First things first: you shouldn’t have an anchor tag wrapping around a div, not only will this not validated, it will also cause problems like the one you are dealing with.
I would do something like this:
width: ; /* up to the search box */
height: ; /* height of header */
You may need to work in some absolute positioning to get it to sit properly, but that’s what I do for nearly every project.