Apple only allows carriers to request an unlock on a phone that has been synced to iTunes with their SIM in it. iTunes will only allow an AT&T iPhone to sync with an AT&T SIM, so O2 or Orange would simply be unable to unlock the phone.
What if I use ultrasnow to unlock and then sync with an O2 sim, then ask O2 to unlock it?