Thousands of pictures including "naked selfies" have been extracted from factory-wiped phones by a Czech Republic-based security firm.
The firm, called Avast, used publicly available forensic security tools to extract the images from second-hand phones bought on eBay.
Other data extracted included emails, text messages and Google searches.
Experts have warned that the only way to completely delete data is to "destroy your phone".
Most smartphones come with a "factory reset" option, which is designed to wipe and reset the device, returning it to its original system state.
However, Avast has discovered that some older smartphones only erase the indexing of the data and not the data itself, which means pictures, emails and text messages can be recovered relatively easily by using standard forensic tools that anyone can buy and download.
The company claims that of 40,000 stored photos extracted from 20 phones purchased from eBay, more than 750 were of women in various stages of undress, along with 250 selfies of "what appears to be the previous owner's manhood".
There was an additional 1,500 family photos of children, 1,000 Google searches, 750 emails and text messages and 250 contact names and email addresses.
The company said: "Deleting files from your Android phone before selling it or giving it away is not enough. You need to overwrite your files, making them irretrievable."
It was not made clear by Avast whether they extracted data from all 20 phones.
Destroy the phone
Google responded that Avast used outdated smartphones and that their research did not "reflect the security protections in Android versions that are used by the vast majority of users".
It was recommended by Google that all users enable encryption on their devices before applying a factory reset to ensure files cannot be accessed.
This feature, said Google, has been available for three years, although it is not enabled by default, which could leave less tech-savvy users open to attack.
Apple has had built-in encryption for its hardware and firmware since the release of the iPhone 3GS.
The hardware encryption is permanently enabled and users cannot turn it off.
Additional file data protection is available, but must be turned on in the settings menu.
Independent computer security analyst Graham Cluley said that if a user is serious about privacy and security they should make sure their device is always "protected with a PIN or passphrase, and that the data on it is encrypted".
However, Alan Calder, founder of cybersecurity and risk management firm IT Governance, told the BBC that erasing data, even after it has been encrypted, will not be enough to completely protect your device.
"Google's recommended routine for protecting the data only makes it harder for someone to recover the data - it does not make it impossible," he said.
"If you don't want your data recovered, destroy the phone - and that has been standard security advice, in relation to telephones and computer drives, for a number of years. Any other 'solution' simply postpones the point at which someone is able to access your confidential data."