My first hack at a solution would be simple and low cost. Each company should ask the customer for personal validating information or even a basic keyword that only the real company should know. We need more than the blatantly poor choices of mother's maiden name, pet name, or city we were born in. It should be something that only the user knows, such as a PIN, a password, or a passphrase. What a pain it is to be encumbered with yet another secret that I have to write down or remember. But better that than financial fraud and identity theft.
When the company calls, the rep should start by telling the customer the company name and the customer's shared secret -- a kind of server-side validation. We do it with HTTPS-enabled Web sites and e-commerce transactions. Why shouldn't we do it everywhere that sensitive information is at risk?