I upgraded too from Desire Z to Relay, didn't even realize any 900 Mhz problem. I get always an H or E icon (HSDPA or EDGE), so 900 MHz should be working.
According to specs, the phone should work with these networks:
2G Network GSM 850 / 900 / 1800 / 1900
3G Network HSDPA 850 / 1700 / 1900 / 2100
I have it in Telekom in Slovakia and in the meantime I travelled to NY and got no problem at all (I had it set to manual network selection to save roaming charges).
The phone I bought via ebay was locked (even the seller described it as unlocked) but after firmware downgrade I easily unlocked it. I recommend LiquidSmooth ROM, you'll fall in love with that phone!
My other finalist was Moto Photon Q, it supports GSM but lacks SIM card slot. If you want, there's a guy in Prague, the author of the sim card mod instruction post on xda, that can do it for you. But I chose the easier way. Now I have a small problem with display flex cable (probably too much openings/day) so I'm considering buying another Relay before they're gone with no decent qwerty phone around. And I can leave the current one for spare parts. I had to put away my DZ because of the keyboard. Some keys started to write several characters instead of one and there was no easy way to fix it.
FYI ebay deals in your name with customs, so they charge you immediately and the phone is delivered to your door without customs holding it for a week.
If you wish to
EU import of Samsung Galaxy S Relay 4G (full qwerty android!) running LiquidSmooth! (currently C902i until I fix the screen cable... doh!)