Competition regulation in many EU countries require apple (or providers) to unlock any handsent with some restrictions (you may have to prove you've waited a certain time, or you are required to pay a fee etc), but I know that in France for example the provider that sells the iPhone there is required to unlock any handsent provided it was sold at least 6 months ago, for a 100 euros. Even if it wasn't bought/sold in France.
Some countries like Belgium don't even allow sim locked phones (or used to not allow) and some carriers sell them with out sim lock by choice in others, like Slovakia, and then some other countries I think can only unlock phones that are locked to a certain providers network, like Hungary T and Voda I think can only unlock T and Voda iPhones respectively, but perhaps phones bought on other networks (Ie T-mobile Germany, or Voda UK or New Zealand or whatever) some of these services maybe taking advantage of these work arounds. If this is the case, these unlocks are legal and Apple has no legal way of relocking these phones. IE in france they HAVE to unlock your phone even if it is ATT... or one would think so logically. Although this info maybe off, but it was definatley the case during iPhone 3g sales...