Hi!
Does this happen if you put the search to a different position?
Do you have a working example page of this maybe? I would like to check the problem closely as I could not find missing closing tags in the code. Or you can copy/paste the whole header.php code to http://pastebin.com/ and maybe I can discover something.