Bear minimum is a factory reset however that would probably leave a bunch of data in the various file copies SD technology keeps.
Not entirely sure how you get around this but after a factory reset try filling the internal storage with data (music or video files, say) then deleting the data. Do that a few times, then do another factory reset and with luck, you should be good.
Of course, you also probably want to keep any SD card you use.