In Internet Explorer a <select> element is rendered by the operating system, not the browser, and so very few CSS properties work on it. You basically can't change the border or button at all - the best you can do is change the font, I think.
I started making a DHTML select menu once, but it's a dangerous thing to mess with - I couldn't get it so it perfectly emulated the native behaviors of the widget in each browser, because only Firefox reported enough events to do so - some states and movements simply couldn't be captured. Without perfect emulation of mouse and keyboard behaviors it creates usability and accessibility problems, so it's not safe.
We basically just have to live with it, I think - select elements are not pretty, but to end-users their predictable - they look the same as they do throughout the operating system - and that's ultimately more important.
"Why bother with accessibility? ... Because deep down you know that the web is attractive to people who aren't exactly like you." - Joe Clark