Like Pete, I have switched to Thunderbird as my primary mail client on both my Windows and Mac OS X machines. It works, it is fast, and it is the same on both platforms without punishing me in order to do so. Worth checking out.
Thunderbird is also a go here.