Did you phone in on a landline from a place reasonably connected to your previously reported identity, such as your home?

You should never accept the caller id of a phone number that called you as identity verification. It is trivial for anyone with a VoIP line to set caller id to whatever they wish.

Exactly! Or the attacker can use a commercial service like spoofcard.com from any phone.

But the toll free numbers that these kind of services typically operate from have a different system which cannot be spoofed.

http://en.wikipedia.org/wiki/Automatic_number_identification

If you're calling from VoIP, the only information is what's passed in the SIP headers. Spoofing works, even to toll free numbers.

Source: I work in VoIP, handle hundreds of thousands of 1-800 numbers on my network, as well as a lot of calls to toll-free numbers.

This makes sense why American Express automated prompt keeps telling me that "I can see the number you are calling from matches the number on your record" (or something like that). My first thought was how trivial it is to spoof the system. Apparently, they are more clever than I am.

In an unrelated incident, I was talking to T-Mobile when the phone got cut off. They called me back (which was amazing customer service) until the first thing he said was he needed to authenticate I was me. So I was supposed to give him the last four digits of my social. I tried to reason with him why it was a bad idea but ended up thanking him and telling him that I'd call in at a later time.