How to tell if an iPhone is third party unlocked?
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.