How to prevent tracking or hacking of a used phone The used phone's IMEI is clean, so it's not stolen.
Looks like its seller did a factory-reset before selling it.
But how do I make sure that it doesn't have any malware or backdoors, and that its seller can't later mess with it, hack it, track it, or falsely report it stolen?

I know that if the phone is rooted, some anti-theft apps and malware can survive a factory-reset.
To make sure the phone is truly clean, should I flash the ROM, or is there a way to tell if the phone was ever rooted?

I suppose these questions could be asked by a thief, but a lot more people buy used phones than steal them.
You can check if your phone is currently unlocked/rooted in bootloader (volume down+power for a few seconds when phone is off should do it. Otherwise Google for your phone.) I guess there's no way to check if your device was ever rooted.

Indeed, the safest* is to root the phone yourself and flash a ROM. Another advantage of this is that you are up-to-date.

*Of course, there's always the potential risk that rooting fails and your device explodes :)