OK, so I've confirmed that my phone will work in Europe (at least on Vodafone, which all the travel sites say is the best one for travellers in Portugal and Germany; looks like Vodafone isn't in Belgium, so I don't know how that part will work).
I can even pre-order a SIM card so it'll be waiting at the airport Vodafone kiosk when I arrive, which is pretty friggin' handy. Now to decide if I need a voice SIM or if data will suffice.