While it's true that unlocking itself is perfectly legal, most unlocks require software to unlock the phone. The manufacturers and networks heavily restrict who gets access to that, and therefore most unofficial unlocks rely on illegally-obtained software (whether or not the trader knows that). The only option we can offer you on the forums is to contact O2.