I had to open support call to get this.

When files are deleted from a document type folder they are moved to the archive store.
On my server that is /mnt/teaming/data/icecoredata/archivestore/liferay.com
The significant part is icecoredata/archivestore/liferay.com all your deleted files are hidden away in there.
You will need to search for them though, the structure is weird ;-)

The docs read "archiveStore: This is where previous file versions are stored to meet compliance and archival goals." - not exactly full of detail ;-)