They'd be able to deal with fraud much more effectively (and cheaply) if they weren't so busy asking the same legitimate customers for the same information year after year. Yes, the job may be hard, but they're apparently also disorganized and incompetent.

Remembering that the account owner is not himself a fraudster is not the same thing as verifying that the account hasn't been compromised and is now being used fraudulently.

(Granted that the OP's questions seemed to focus on the former, rather than the latter)

Oh snap, you have just saved Paypal millions of dollars and cut several jobs at their fraud desk.

I totally agree with you. It shouldn't be hard for Paypal to get better (and I don't understand why they don't), but to make something new that is better is a far more difficult proposition.

I'm certain (non-sarcastically) that fraud is a Hard Problem. But it's not so Hard that Paypal doesn't make money; why do you claim it isn't possible for somebody to solve the same Hard problem but have non-atrocious customer service?

Paypal lost millions of dollars every month to fraud in the beginning. Not a lot of companies can afford to loose thousands of dollars let alone millions.

I don't think it is impossible, just very, very hard (and expensive), made worse by having an entrenched incumbent who has very deep pockets.