If you do a good amount of international travel, and want roaming, you'll have to focus on the International phones VZW offers. That's the Storm, the Saga, and the 8830.

Personally, I'd look at moving to AT&T or T-Mobile and getting a GSM phone. Much, much easier for international roaming, and you can buy an unlocked Touch Pro or similar phone without any problems. AT&T should have pretty good coverage in your area. And if you buy a completely unlocked phone, there's literally nothing you need to do to make a different SIM work than plug it in.