If you want pure phone functionality and you don't need data, then I would suggest getting your hands on old Sony Ericsson t68i. Best pure phone I ever had, but it predated HSPDA.

If you are looking for small phones that support HSPDA/GSM you just need to find one that is quad band and you will have zero problems in Japan/Korea and on Cingular in the states.