A few weeks ago I lost my card UK driver's license somewhere in Arizona/Nevada.
In November I will be in Australia. My new license may not make it here in time.
However I still have the paper counterpart of my UK license.
I've been told you can drive/rent cars with the paper part + passport? Is this accurate, or do I need something additional to be legal to drive in Australia?
I'm not sure how valid a paper UK license is in Australia. I believe it would be up to interpretation. If you rent a car, you might have to convince them that your paper license is indeed an authorised version of your real driver's license. It might be a good idea to call up the rental car company and ask beforehand.
Road rules and regulations are governed on the state level. Each state has its own rules regarding the use of foreign drivers licenses. Some states require an International License as well. The Australian Government site summarises this well.
As of June 2015 the paper counterpart for the UK photocard driving licence was abolished and no longer has any legal status, the government advice stating that the document should be destroyed.
Based on this, I wouldn't rely on the possession of the counterpart itself being taken as sufficient proof of entitlement for a number of reasons, for example, it no longer proves that your licence has not been revoked (because the government is no longer requiring it's surrender), or may not show that you have a recent serious driving conviction (because it is no longer being updated and re-issued following conviction).
Instead of the paper counterpart there is a new on-line system which you can use to provide your current licence details to relevant third parties such as hire companies.
