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 :)
For most phones, there is a way to flash the factory image (not to be confused with just wiping data) supplied by the manufacturer / ODM. Once flashed, compute checksums of all partitions (except cache, userdata and internal sd if on separate partition). To compare them, find the checksums for this phone and factory image somewhere or ask any owner of this phone to compute them for you.
Computing checksums may require root though, so your /system partition will be modified anyways. But since flashing the factory image usually wipes it, you should be safe regarding this.