You're right. Its is crowded up there in MSIE and a big space in Firefox. Check your CSS for the search form to see if there is anything in there that might be a clue.
I know that Firefox has problems with float divs inside of non-floating divs...but I'm not sure if this relates as your search form isn't a float. Have you put a border around the different areas, like the column, search container, calendar...etc., all different colors (red, green, yellow - messes things up but helps you find the parent/child relationship in the containers) and see if there is another container that is getting in the way.
I'd also check to see what the stuff is about the way Firefox handles padding and margins.
You can blame the form, but the colored box around it looks fine. I think it is the way the form's container might have some extra padding or margin that Firefox interprets as more than should be there, or there is something about the bottom margin or padding of the li that the search sits in.
Try removing the search from the li and see how that works for you.
Hit and miss, but I hope one of these things helps or leads someone else to have an answer.