The Gevey Ultra S unlock for the iPhone 5.0, 5.1 works with the Verizon iPhone 4S, but I'm going to warn you--it's pretty sketchy. When you reboot your phone and/or lose signal and try to renegotiate a lease onto the network, it takes several minutes (like upwards of 5 in most cases) to connect. Also, when you reboot your phone, it prompts you to Accept their license agreement like 30 times before it does anything--and once it actually believes that you accept the license agreement, you have to wait for it to actually connect.
I do not recommend this device. It's pretty hacky. I only recommend it if you REALLY know what you're doing, and you REALLY like pain. That said, it does work with TMo most of the time once it's connected.
One other thing: Picture messaging. The iPhone doesn't see to keep your cellular data APN and MMS server settings with the Gevey installed. The instructions for changing these values manually means that you have to reboot your phone at the end of the process--and the reboot resets these values. Picture messaging does not work as a result.
Also, Tmo 3g/4g data is restricted in most areas of the nation to the 1700 Mhz bands, which the iPhone 4S does not support this spectrum--it only works on the 1900 Mhz bands. Not a big deal for me, but something of which to be aware.