Is flashing a new ROM enough after phone was stolen?
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.