Yes, unlocking services do work for some of the phones, it's just a risk if they don't, and there doesn't seem to be a way to tell! Was this a used phone? There were some claims that the first batch of phones didn't have the lock code changed so unlocking services work with them. But no real confirmation of that.
If you don't have a fall-back (such as someone in the US who can/will get VZ to unlock the phone for you) then the YMMV when buying the phone from a third-party really comes down to: "If I can't get this phone unlocked, how much of a [expletive of your choice] would that be", and, paraphrasing Eastwood: "Do you feel lucky today!" If the price is low enough, might be worth a chance....