Chris from Mobiletech Addicts let us know that O2 is coming through with the iPhone unlocks. Once their web form is submitted, they send a text (it took all of 15 minutes form him), then:

I put in a Vodafone Sim Card into the phone and fired up iTunes, a couple of minutes later and the [above] message appeared.

Congrats UK residents, you're free at last!

(Now if only Rogers Canada would find a pair and do likewise right...)