Simple: sign your messages. If eBay, PayPal, CitiBank, and friends just signed their messages, it would be easy to check if it really was sent by firstname.lastname@example.org and if that link really is to paypal. Additionally, it makes it easier to catch the sender of the messages. It wouldn't be perfect, but it could help.
Phishing aside, start giving me the option to get my emails encrypted. I'd rather not have receipts sent in plain text.