Just letting everyone know that I have successfully unlocked a Vodafone iPhone that was purchased outright, without a Vodafone account.
If you are not a Vodafone customer, there is obviously no account that they can add the $75 unlocking fee onto.
I purchased a $9.95 Vodafone Sim starter pack and also $70 credit to start off with. The starter pack gives you $10, and combined with the $70 worth of credit, tops the pre-paid account up to $80.
I contacted Vodafone on 1300 650 410, and told them I needed to unlock my iPhone. Give them your Vodafone pre-paid phone number and passcode (This is set up when the pre-paid sim is purchased).
$75 will be deducted from the account, and you have to give the IMEI number to the operator. This then gets sent to Apple and the unlocking process continues from there.
I rang Friday afternoon and was advised of a 3 business day wait until the phone will be unlocked. I just restored the phone this afternoon (Tuesday) and placed an Optus sim in it and it is already unlocked.

This may help those of you that purchased an outright locked iPhone from Vodafone (when they were available), or if you purchase a Vodafone locked iPhone off eBay or a forum etc.