My Sony Ericsson W610i has push-imap, and it works really well. It also worked whilst I was in Philippines, but its quite expensive on PAYG -Vodafone roaming charges are eye-watering, I'll get a Smart SIM next time I'm in Phils and see if I can get it to work with email.
I'm using Google Apps as a second-store for my email (emails get delievered to my Tuffmail account then forwarded onto to Google Apps) I then use my GApps account to get emails on my phone and/or if I'm away from the lappy.