Yes. It is possible. The topic at the top of this forum is obsolete now. I've unlocked my iphone from a 1.1.2 OTB iphone down to 1.0.2. (only major difference is lack of wifi istore) and it worked perfectly with any network.
However, i reccomend using the guide below if you want to use an o2 sim. It doesn't unlock, it just activates. This will only allow you to use o2 payg sims, not other networks.
http://hackint0sh.org/forum/showthread.php?t=15849
Add me to MSN if you need help (encore2k6@googlemail.com)