>When PayPal or your bank or another large organisation send you an email it should be signed. Then you can verify it is from them.
The problem for the layman user though is that PayPals.com (fraudulent) can also sign their emails -- and they'd be conditioned to equate "signed = legit" (and can easily miss misspells, alternative domains, etc).
I see only one way around that, and it's prohibitively expensive: have the user assign aliases to public key signatures, and mark everything else with a big scary "UNKNOWN".
And I'm not even sure it would work: many users would just click the "yes I know them, please trust" button on first use.
An alternative would have "unknown" be a little, not very scary warning (with easy TOFU), and the "this handle looks like this other one, they may be trying to scam you" blinking red warning. Then it would be on the developers to detect typos and look alikes.
The problem for the layman user though is that PayPals.com (fraudulent) can also sign their emails -- and they'd be conditioned to equate "signed = legit" (and can easily miss misspells, alternative domains, etc).