The earlier bits of the VIN should be specific to the car, so a random change should be noticeable. I.e. if a Q denotes a V6 and a W is a V8, be wary of a car with a '7' there.
If they were clever enough to swap to a known 'good' letter/number, it gets harder. The latter part of the VIN is a chassis number and should be unique to the car. That's why dealer parts departments normally just ask for the last eight of the VIN. What sucks is that I don't think CarFax will care about duplicate chassis numbers....but it shouldn't happen.
Obviously, they can just 'accidentally' give you the VIN of an existing clean car...but how would they go about making new records for a VIN that previously had no history? Is CarFax actually so shitty as to allow that to happen?