I'm in a similar boat. I have a Pre2 with Verizon, and I've been having trouble with it lately...missed calls, missed texts, missing calendar events, sluggish behavior, locking up device, and of course I've always had the infamous Verizon GPS Palm issues.
Anyway, I can't continue having issues since my company provides my phone. They need reliability and my current phone isn't providing that. They won't let me buy a Pre3, too risky in their minds. Given the state of things, I have to agree. So, I am left with what else is out there. I do not care for the limited interface options for iOS, so I am looking at Android.
I have considered the Samsung Galaxy SIII (S3) and the Samsung Galaxy Stratosphere II. The Strat II has a horizontal slider physical keyboard, and isn't too big. I think it comes with Android 4.1 Jellybean, which might make it a Global Ready phone. I think there might be a free offer at Best Buy on this phone at the moment.
The S3 shipped with Android 4.0 Ice Cream Sandwich, but I read some articles that said 4.1 Jellybean was rolling out starting on 12/14/2012 which should also make this phone Global Ready. There was a sale yesterday at Bestbuy for $49...today it is $149, but still $50 off the Verizon price.
Anyway, that is what I have been thinking...good luck, I don't have any info on the new Windows OS mobile.