I work for a Credit Reference Agency (but I am not speaking for them here). Just because the CRA says "We have no record of this person" doesn't (and shouldn't) mean they don't exist.

It's up to the card issuer whether "the customer might not even exist" is a risk they are up for taking.