Surely this is not possible (assuming the recently deleted folder is cleared)?
I know it could be done with insecurely erased hard drives but I dont think any phones are using those?
It is indeed possible, recovering a fully deleted file or even chats logs is the easiest part, given it’s unlocked. I don’t know about Australia, but plenty of law enforcements use cellebrite (1), and there are other tools too that provide such forensic analysis.
(1) https://cellebrite.com/en/home/