How to tell if an iPhone is third party unlocked? Is there a safe way to find out if a used iPhone is intended to work on a particular carrier or is factory unlocked VS. having been unlocked by a third party?

I'm on the Rogers network. I'd want a phone intended to work on the Rogers network, or intended to work on any network, rather than one that might become relocked by a future update. (Also, I had a third party unlocked phone once before, and it liked to spontaneously restart. I don't think that was a coincidence.)

Jailbreaks don't concern me, since I can always revert those. But having a hacked baseband is something I'd want to know about.
For a 3GS, you need to avoid the 06.15.00 iPad baseband, which is easy to check.  As far as I know, all other unlock-related baseband hacks consist of preserving old versions of the baseband - which is easily remedied by updating to (or re-installing) the latest firmware.  

You can also match the latest iOS version and baseband for that device, as listed here.

iPhones might also be unlocked with a Gevey sim card interposer, which replaces the SIM tray, and so is easy to check for.