Because it validates doesn't mean that it should be working, your style logic needs to work out aswell. Maybe your logic is right yea. If it was about validation I could easily produce some IE only pages with valid XHTML/CSS ;)
Resets don't always fix problems with layouts, they just provide you with a normalized base to work from... in a lot of cases, far more normalized than you need - it's almost like frameworks for CSS. Snazzy, but if you don't need the bloat, don't hop on the boat... er, bandwagon. IMHO.
Spyke, the problem with your page in this case is how IE's rendering your img... since the ID is part of the IMG itself and not a DIV that wraps it, IE feels the need to add some whitespace after itself. I would,
a) add a line break <br /> directly after your IMG element (on the same line in the file)
b) remove the ID from the IMG element and wrap the whole thing in a DIV with the same ID (will cause your border to render farther out, until you specify a new width, but will fix your whitespace problem)
c) modify your logic so that the border necessary to the menu is permanently attached to the menu (such as by adding a BORDER attribute to your UL#menu), which would also have the future benefit of allowing you to remove other elements without breaking that one.
d) get rich, buy Microsoft, and do us all a favour and discontinue internet exploder. :)