edit: I'm not sure that GC to Skype forwarding will work. Actually, I got it confused with Gizmo. You can forward GC to Gizmo. Look here:http://lifehacker.com/software/telep...ect-313937.php

You can get a Skype-In U.S. number to get Skype calls abroad though. Sorry.
End of edit

This may be too much info for you but I'll try to answer your questions.

I am not sure about Verizon data allotment. I will tell you that if you try to use your Verizon phone abroad you will get taken. Companies charge a lot because they use local wireless companies to route your call/data and because they can. Kinda like ATM fees when you don't use your bank's own ATM. If you are on wifi on your phone, you will not be charged for data. If you have an unlimited data plan with your cell company here, you will get charged abroad for data because you are using another company's network despite the fact that Verizon is billing you.

Windows Mobile phones support Skype. It is free to download. You can place Skype calls from your Win Mobile Phone through wifi. Make sure the phone you use has integrated wifi if you decide to go this route. Some phones from ATT/Cingular are ATT 8525 and ATT 8925 (Tilt). I'm not sure about Verizon or other carriers.

You can buy a 800/810 tablet and use it for Skype as long as you have wifi available. From what I understand, wifi is available almost every where in major European cities. Try to get a Grand Central phone number with a US area code of your choice. GC allows you to forward calls to Skype directly. This can be configured on their website. This will allow people in the US to call the local GC number which will get forwarded to to your Skype number that you can pickup using your Nokia 800/810 (or whatever you use to get Skype) anywhere in the world (assuming you connected via wifi), and it is free. Sign up for a free invitation at www.grandcentral.com. They don't charge now but may charge a reasonable rate in the future. GC is in beta right now and is owned by Google.

Finally, if you still need a phone here in the US and want to use it abroad then I suggest that you switch from Verizon to ATT/Cingular or T-Mobile to get a new phone (new 1 year plan req). These two companies use GSM bands which are used in Europe and the rest of the world. Make sure you buy a Quad band GSM phone with these companies and request an unlock code (aka subsidy code) from your new provider after a month of good standing. Tell them that you are traveling to Europe and want to use a local SIM card. When you successfully unlock your phone you can take it abroad and buy a prepaid SIM card in Europe an get a local number with local data/phone rates. Your phone will still work in the US when you comeback. Also, it doesn't matter if you choose a regular phone or a Windows Mobile phone, just make sure it is Quad band. You can't unlock Verizon phones.