Indeed, with phone reps at any company, it can be too easy for someone to scavenge a little bit of information here, a little bit there, until exactly the kind of situation that happened to you. I don't know what EA's policy is now, but it was pretty darn secure when they required at least a few things from name, account name, credit card/address, e-mail and CD code. Even so, it's still only as strong as the rep who's weakest in policy.
I think I've mentioned before that a friend got his account back, though he didn't have the CD code, couldn't give the old credit card number after being away a while, and he was one letter off on his account name. This was a very long time ago.