Why doesn't PayPal and other services add a Verified Paypal code to a user's account page. And train users to login during these phone calls and ask the caller for the code?

The training itself - if you're being verified, you should do the same of the caller - would have immense societal value.