So far we have no former TWHS for Australia. While reading a IUCN document I found reference to an indicative list from 1991.
https://portals.iucn.org/library/sites/library/files/documents/2013-026.pdf (page 202)

It includes:

Cape York Peninsula
Eastern Arid Zone (including Channel Country, Gibson Desert and Lake Eyre)
Forest and wildflower regions of West Australia
Antarctica (!)
Alps and eucalypt forests of South East Australia: Australian Alps and East Gippsland National Parks
Nullarbor

Looked into this one suggested by Assif, it is indeed an interesting study.
However, I do not think they are former TWHS:
If I read the document well, these I believe represent an earlier stage (the Australian Indicative List), but never were accepted as a Tentative List:
"led to the abandonment of Australia's Indicative List in 1995 before it had been submitted to the Committee."

We know what the tentative list looked like before 1995 and these were not there. See for example 1994, http://whc.unesco.org/archive/1994/whc-94-conf003-inf7e.pdf, where it is said that Australia's list did not meet the requirements.