My Sony Ericsson T610 has done an excellent job thus far over here in Europe. It is a traditional tri-band phone, with support for 900, 1800, and 1900. I use TMobile back home, and used an O2 SIM over here for a time.

I'm going to look for a quad band SE phone down the road, so that when roaming in the US on Cingular, I get the best reception. Roaming here and seeing 4-5 GSM providers at any time is awesome. US cell companies should be forced to a single standard.