the 4G network that sprint is advertising is something else, from what i gather it's similar to t-mobile's recent speed increase (not the same thing technically, but i think the end result is the same, someone correct me if i'm wrong)
verizon's LTE network which is still a little way off (in my eyes) is the true "4G" network to roll out, but none of the phones out right now will work on it in the sense of really utilizing it. LTE should be completely backworks compatible, so the phones will work, just not on 4G, similar to the original iPhone not being 3G, but working on AT&T's network. Or all the EVDO rev.0 devices on verizon's network.
so you'll have to buy a new phone to really use verizon's LTE networking, but most likely by the time it's really out and ready, it'll be time for a new phone anyways.
the storms and tour are all world phones, the are both CDMA and GSM, so they will work overseas where there (depending on where you go) might not be any CDMA coverage, as the GSM format is more popular.
from what i gather, if you really need a phone (and want verizon to provide it) they used to (still might) offer int'l loaners (at i'm guessing pretty high prices) that you can ask them for.
personally, if i really need a phone, i have a decent quad band gsm phone around somwhere i'd just buy a prepaid SIM for over there and use that.
if you travel overseas a lot for business or something, you might want to consider one of verizon's world phones so your number wouldn't change and it would be a pretty seamless experience.