ALL cars that come out of Japan have dereg papers etc which MUST show genuine kms and all sorts of other details about the car. This is the BARE MINIMUM you should ask any dealer for. If they don't/can't provide this then definitely walk away.
A LOT of yards based in Sydney doctor the kms (a guy in Sydney comes in with his laptop and changes the km in 5 minutes for a fee of $100)- it is easy as hell to spot how old these cars are - and they STILL advertise V35s with 25,000km on them - they have a yards full of them - yet when I was shopping around the Japan auctions for V35s I almost never came across cars with such low km. they also hold heaps of spares and can 'make' you a premium in a few hours with leather seats (half or full, your choice), pop-up TV, premium wheels and Brembos, depending on how much you are willing to pay.
I ended up buying a V35 from a dealer in Sydney that is a bit more reputable than most, and despite the disk rotors being WAY more worn (and badly lipped) than a 48,000km car should have, the rest of the mechanical checks I had done were good, so I bought it. But not before knocking him down $6k plus free delivery to Adelaide off his original price!