Scan all local Police cars. Install readers around Thugs HQ.
A barcode or an RFID tag? The only reason most of your products don't have an RFID tag is that barcodes are much cheaper, and the entire logistics chain - from manufacturing to retail - is already pretty well optimized around those. There is not much value to gain. About the only use for passive radio tags I've seen widely deployed is theft prevention, and half of the times the tags are removed at the counter and later reused.
(Source: I worked on a software that reads those barcodes and controls the manufacturing process.)
Barcode would absolutely allow you to differentiate between any two cell phones, or cars, or computers.
My reading is that Tirerack registers the DOT Tire Identification Numbers with the tire manufacturers. Not with "the government". It's the manufacturer who is liable for damages from defective tires. So it's the manufacturer who needs this information.