Yep... the classic struggle between overall project resolution and screen resolution.
Sometimes we need to be creative about how we create our projects. Perhaps recording initially at full screen, then scaling that to something suitable. Sure, it's gonna get fuzzy when you scale it down. But if the goal is simply to orient the user as to what area of the screen we are placing focus on, maybe that's okay. Then you could use a zoom area to make it appear as if you are zooming into a quarter of the screen where you could record in full detail.
Personally, I don't believe there is a "one size fits all" approach and it seems this is more art than science. I've seen many users say that 800x600 is the size they use.
Keep in mind that the larger you record, the larger that directly translates into produced file size. And that directly translates into how well things will perform while you are editing in Captivate as well as how efficiently it does (or doesn't) stream down to the end user's PC when they view.
I would encourage others will chime in here with their own observations.
Helpful and Handy Links
Long ago I found that 995 x 627 was the best capture size for end-users on 1024 x 768 screen resolution.
I wrote a blog post that documented reasons why I settled on that as the optimal screen capture size for Adobe Captivate projects.