Can't really tell without seeing your site... but having a floating #navMainWrapper sounds a bit strange (at least with the common structure for zen cart templates).

Try "text-align: right" instead?
Or try transferring the "float: right" (or "text-align: right") to #navMain instead, or to #navMain ul... etc... in other words try experimenting with the child elements.

About the search_header - it's a notorious snag with many browsers that enjoy adding extra linebreaks at the beginning of a form element for no reason whatsoever.
Can't really help much with that - you'll probably have to tear open the template file itself and restructure that section...