You tell that you tried all settings? Are you talking about the slide quality in Captivate? Can you check that, because the default quality is Low 8-bit. Either you change that quality on slide level, or you can override the present quality on publishing by unchecking 'Retain Slide Quality' in the Preferences, Project, SWF size and Quality (see screenshot, highlighted in yellow). If this is not giving the expected result, you could also uncheck all compression options (highlighted in green, not unchecked here).
The things I tried were the capture settings, the publish settings and based of your response I also tried the individual "slide" property settings. It still is giving me those lines regardless of what I do, when capturing it.
I just tried "importing" (which in previous versions never worked -- made it blurry) and even though within the software it's blurry-ish, published, it's very clear. I only had to "manipulate" one slide because of changing the size (920x... vs 800x600).
Forgot to ask: hope you were not talking about Full Motion Recordings? If yes, you have to set it to 32-bit (Preferences, FMR).
Second question: rescaling will always lead to quality loss, did you rescale?
I did reset it to 32-bit in the recording settings before I recorded. No I didn't rescale anything. I ended up going back to Captivate 4 for now to finish my project.