Bangkok would be a great place to go phone-hunting. As mentioned earlier, Japan is out of the question, and I'm not so sure if Singapore sells open-line phones.

And I loved the T28. It served me well for two years before it became too slow. I'm still using Sony Ericsson (Z600 at the moment), though it doesn't have the battery life my T28 had...