A friend of mine had his Samsung Galaxy S 2 stolen and returned some 20 minutes later after he talked to the pickpocket and tried to play her guilty consciousness.
USB debugging was active when I checked with the old ROM, so I assume that everything was possible. The bootloaded was already unlocked, but the phone was not rooted, as far as I can tell.
I flashed Clockwork Mod Recovery and then Cyanogen Mod onto the phone, and formatted the external SD card with
mkfs.vfat on Linux. Is that enough to get any malware off the phone?