Suppose you get a letter, with your name and address on it, asking you to call an “Investigations Manager” for retail finance outfit. The number appears to check out, although forum posts seem to come down 50/50 on ‘is this a scam or not’.
You call the number and get given another number – again, the crowd is split. The “official body”, CIFAS, is even less useful…
You call the second number and immediately they start asking you for personal information “so they can check it against the data they were provided with” that was used to set up a potentially fraudulently created account.
This is wrong, wrong, wrong; broken, broken, broken.
There are no trusted parties either side of this exchange.
The company (C) and the individual (X) don’t trust each other, and neither trusts giving the other information about the individual because: the company doesn’t know the individual is the individual, or the hoaxer; the individual doesn’t know the company at all.
What C wants is personal information from X, so that it can check that information against its records. But X doesn’t trust C, because C may just be phishing.
What X wants is the information that C reputedly holds about X, so that X at least knows whether C has true or false information about X. What X does next is moot, if they don’t trust C anyway. In fact, there is no obvious way for X to develop trust in C except by using public keys, such as phone numbers on websites that X trusts.
One solution might be to go to a trusted party – such as a high street bank, B. If B has a trusted route to C, and also data on record about X, X can go to B, who will relay to C that X is known to B; B passes C’s reference about X to C, maybe along with a single confirming piece of information. If C trusts that B is in the presence of X, and X grants permission to C to divulge information to B, then C might divulge what it knows about X to B, who is the only party both X and C trust in the exchange. But there’s still a problem, because B may not be trustworthy, and may not be in the presence of X (consider a corrupt bank employee with access to X’s records and an accomplice willing to pretend to be X).
Hmmmm…
See also: “For Data Protection Purposes”, Can You Give Me Some Personal Data…
OUseful.Info, the blog... 
There’s a trusted route for this kind of identification in Germany: It’s called PostIdent and essentially works like that. The company C sets up an account with the German, formerly federal, post office (that would be B in that case). If company C wants to verify person X it can start a procedure (paid by C, around 30€ per investigation afaik –> so even if one comes around the verification procedure it should be to expensive for phishing), were person X hast do come to a post office and legitimate himself with a valid ID (passport or identity card). After that the post office gives the information back to C that X is X.
We are obliged to do this here for every bigger financial thing, like opening a account, applying for credit and also for everything were your age has to be verified (mainly shooter, horror and adult movies/games, but also things that could serve as weapons as knifes etc.) – On the pro side you normally can sent all the paperwork in for free in a envelope which is provided to you if you have toc come to the mail office if you have to do the PostIdent…
How about asking for things like “What is the 3rd letter of your X?” Enough random info to establish it’s correct but not enough to be useful for a phisher.