As you suspect, a Cingular 3125 will certainly require SIM unlock to work with a Vodafone SIM (will need that for any SIM other than Cingular SIM). But as deecee52 notes, it is quad-band, which means it has all the the 900mHz+1800mHz goodness to work all over Europe (the other two bands in the "quad" are the US 800+1900). Just like your Qtek 8500 would work fine in US with SIM unlock and US SIM (all the StarTrks have 800+900+1800+1900 bands).
Your thoughts about the improvements in the 3125 are dead-on. I find that the battery life in my 3125 is fantastic, and it has a ton of available storage memory, even after all the extra junk that Cingular has put on it. When I go to Settings > About, it shows 52MB of available storage (and I have a number of apps installed, including PocketPlayer, Windows Live Search, Google Maps). But keep in mind that the beefed-up battery adds a few millimeters of thickness to a hump in the back, versus the sleeker Qtek/iMate/Dopod versions (doesn't bother me, I still find it plenty slim)...
All that being said - if you are not already doing so, you might want to keep an eye on "HTC Erato" (aka HTC S420, aka HTC StarTrk the Next Generation), which it is rumored that HTC will be rolling out starting next month. That is, if you want a new flipper with WM6, 3G HSDPA data, GPS, and FM radio capability (at least those are in the leaked specs - nothing officially announced yet)...