You're so much better going with Vodafone then. None of that nonsense of waiting 3 months and I've also heard stories about Orange not unlocking some iPhones are 3 months too.Orange and Vodafone charge £20. I believe O2 do not charge for unlocking an iPhone, but might be wrong.
Do Vodafone sell them on PAYG in stores? That's the big question now, if so £20 more for not having to wait a few weeks for an unlocked one isn't that bad.