I've done that to credit card companies that I even called. They'd say something like "okay I need your full social security number" and I would just say no. There would be a pause, then they would say "okay I can verify you by your recent transactions."

Like why didn't you start with that! Some companies just don't teach their reps to care about security.