A lot depends on the country you live in also. As an example if you live in the US and are looking to purchase on, going through MotoRex or RBmotoring is a safe bet!
The same for New Zealand and Australia. Here in NZ and I would imagine in OZ cars can not legally enter the country without Degreg papers from the country of purchase, such as Japan. Even though those can be forged odds are the business that is doing the dodgy deal will get caught.
Each skylines has a unique chassis number and also the letter is unique to that particular model. Such as BNR for a GTR, HRC for GTS, GTS4, GTS-t in the R32 range. Remember though may cars are modified in Japan also with kits, and bits from a GTR onto other chassis, so what may appear to be a stolen car and done up to hide it, may be infact a car someone has doen up.