This thread describes the situation I was in, in case anyone stumbles on it later.
I tried via the O2 online chat to get the phone unlocked. They said that I could not unlock it because they could only supply an unlock code if the phone had been used for 12 months on O2 and their records showed that this particular phone had only been used for three months. So, it looked like I would have to get a UK O2 SIM and use it for nine months. That is not easy if you live in Australia. However there is a site called Travelgear that sells O2 SIMs and lets you charge them up with 20 pounds of credit. So, I did that, and installed the SIM with a view to seeing out the 9 months, perhaps sending a text every so often and topping up each month. After installing the SIM I received a text from O2 saying I had 100MB of data to use. In trying to work out the status of the phone account I pressed an O2 shortcut on the front screen which opened up an app which when I pressed on the "My O2" button, opened up the web browser, which would not let me log into any information. Then, I thought I would ask O2 again to unlock via their online support form. Unsurprisingly, they responded that they could not but surprisingly, they said that the reason was that I did not have the necessary 15 pounds of credit. I queried that because I thought I should have 20 pounds. Ha ha! While it is 100MB, it is 6 pounds per MB if you are roaming in Australia! The brief attempt to check my account status had wiped out my credit. Gosh how I laughed.
Anyway, in parallel with all of this I tried an unlocking site called gsmliberty. They said they would need to go to a "second level database" at an additional charge and I said no thanks I will have a refund, which they promptly gave without fuss. Then I tried CellUnlockerPro. First time, they said the servers were down, which I thought was just an excuse for not being able to get the unlock code as gsmliberty had not been able to, so I asked for a refund and they too gave it to me promptly. About a week later CellUnlockerPro emailed to say the server was up so I thought nothing to be lost and gave it a shot. I put in the wrong IMEI but again CellUnlockerPro gave me a refund because I spotted the mistake early. I tried again and lo! they gave me an unlock code which worked.
So, moral of this sad story seems to be that if you are in Australia, do not waste money trying to get the free unlock out of O2, just spend the 30 USD that CellUnlockerPro charges.