first...read this for getting your phone unlocked with big red
http://forum.ppcgeeks.com/showthread.php?t=91599
second....i suggest you just buy a local pre-paid sim card at the country where you're going to be at. international roaming charges aren't cheap for voice calls. data is a different story. check the local carrier to find out how and how much they charge for data using their sim card. or you can check with verizon if they have international data.
enjoy your vacation!!
edit:
btw...if you use data during your trip, you're connection would only be EDGE.