Fang's code is the fix for IE6, however it still breaks in FF when font size is reduced. This is due to the total height of floated #headerleft div being 2px more than minimum height set for #header (89px + 2x1px border + 2x18px margin = 127px). So if you change css to
height: auto !important; height: 127px;
it should work.
Actually, if the graphic had the border outline as part of the graphic, and it was used as background for #header div, then #headerleft would not be needed at all (and this problem would not have existed).