You should be cautious and skeptical of most services that offer a "factory unlock" in my opinion.
The cellular carriers all maintain a database of phones that when iTunes asks - gets told to factory unlock the devices. Since that database is under their control and they have a business relationship with Apple, any entries that are placed in that database in a fraudulent manner could easily be found and reversed.
Your money spent for the "factory unlock" might work if the sellers have a legitimate business relationship with the carriers and it's more trouble for the carrier to allow some people to bypass their paywall and policies, but my guess is most of these unlocks are shady to illegal and I'm surprised that the carriers don't periodically sweep the database for all active phones that should be carrier locked and are not and send a nasty letter to the owners and re-instate the factory locks.
I'm not one to defend the carriers in general, but I can't see how they would continue to charge $500 or more for an unlocked phone only to allow people to spend $10 to accomplish the same feat. If they're going to roll over for $10 then you'd expect all unlocked phones to sell for that in a short period of time.
So - I'd say - pay the money if you are willing to risk it failing, but going into that transaction with your eyes open might be prudent.