[Giaguara]

In most Europe, they are supposed to sell you the unlock code when you have legally purchased the phone. So if you have a pre-pay or a contract phone, and want to move away from T-Mobile, Orange, Meteor, Vodafone or anything you got it with, they should give you the code. Sometimes they ask you to put some money on the phone to do it for free, sometimes they charge for the code, and sometimes they suggest a store or an unlocker service for it.
So when you have legally bought the phone anywhere, you should be able to use it, as a consumer.

That said... the first iPhone that I actually saw in real life and used was from a Swedish coworker of mine, in France. So he had bought one in San Francisco, unlocked it and used it in Sweden. If I'll catch him online, I'll check what he used for it. Since whether this is legal or not may depend on where you are while reading this or planning to do this for your own phone, if anyone finds out, just in case this might be safest to provide details in private messages. (One place without going too much into detail should be Chinatown ... London or any other, the electronic stores in them)