Is flashing a new ROM enough after phone was stolen? 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?
I think this is more than enough. Flashing your ROM again should be more than sufficient. This not only allows fresh installations of any old apps to prevent spyware, but also dormant any other app data from existing apps to be largely overwritten or deemed as corpses. You can also perform a cleanup using SD Maid just to be sure.