How sure are you about the pre-paid SIM from European providers? FWIW, I'm currently back in Germany (drove through Germany to reach Switzerland, drove through Austria, and back to Germany - all in one day) and made contact with Vodaphone in Germany as well as I forget which provider in Switzerland (made a call back to the States from the city of St. Gallen, Switzerland). I didn't check the Austrian provider's name but got the usual robo-messages from VZW about roaming in Austria, as well as Switzerland, and the return to Germany. And all without a SIM card from Vodaphone et al. I did sign up with VZW for the international data plan, which includes voice and text. And I have a SIM from VZW, installed when I bought the phone. FWIW, even in Germany, I've had support from O2 as well as Vodaphone (on previous trips). If I need a pre-paid SIM for each provider... Not Good.
All of this is on an HTC Droid Incredible 2. I own a Maxx but had to leave it in the States as ICS hadn't been released for OTA update (and GSM support) before leaving the US.