He wiped his old iPhone 5 with a factory reset, removed the SIM card, and sold the device second hand to a private buyer.
"They told me, 'One of your mates called about a gig you were doing for New Year's Eve," Mr Thornton, a Melbourne-based IT professional and musician, told Fairfax.
The new phone owner (also a Telstra customer, who wishes to remain anonymous), explained to Mr Thornton that when the iPhone 5 was powered off and then on again, it downloaded Mr Thornton's voicemail messages to the phone's inbuilt visual voicemail app, where he could then browse and listen to them in full.
The serious privacy breach, which Mr Thornton detailed on his blog, has stumped both Telstra and Apple, although the responsibility appears to lie with Telstra rather than the iPhone maker.
Mr Thornton said Telstra gave him "the runaround" when he first notified them of the issue, telling him it was "impossible".
"They said it can't happen, you must have forgotten something," Mr Thornton said.
"You mustn't have reset your Apple ID, or you left your SIM in the phone [before you sold it].
"I thought, no, I work in IT – I kinda know what I'm doing here."
A Telstra customer service representative told him his only option was to disable voicemail, Mr Thornton said.
After more than 24 hours trying to resolve the issue with Telstra customer service, a senior Telstra engineer apologised to Mr Thornton and confirmed what was already clear: two separate phones were accessing and downloading his personal voicemail.
"He [the engineer] had a direct line to Apple, and [when he told them about the issue] they said, 'We don't believe you'," Mr Thornton said.
Telstra has now implemented a fix which rejects the old phone's automatic requests to download Mr Thornton's voicemails. However the telco has yet to determine the root cause of the problem.
"They know what the symptoms are but they don't know what the cause is," Mr Thornton said.
Replying to a post by Mr Thornton on Reddit, some suggested the problem may lie in Telstra's visual voicemail using a mobile phone's International Mobile Station Equipment Identity (IMEI) number for authentication. An IMEI is a unique number used to identify individual mobile devices.
However a Telstra spokesperson said the telco does not use IMEI numbers to authenticate visual voicemail.
Telstra is understood to not yet have been able to replicate the voicemail duplication issue, but is looking to analyse the individual iPhone 5 device to get to the bottom of the privacy breach.
"We are committed to protecting our customers' privacy, keeping their personal information safe and ensuring the security of their data," the Telstra spokesperson said.
It is unclear whether this type of problem has affected any other customers.
Mr Thornton said he was lucky the person who bought his iPhone 5 had been co-operative and forthcoming about the issue, but was worried about the implications for privacy-critical businesses such as law firms or medical and government organisations who resold their digital equipment.
He said he would "probably not" resell an old phone in the future, even though he'd done so three or four times in the past.
A recent Deloitte survey found 27 per cent of Australians give away their old mobile phones, while 8 per cent sell them.