Jay, you bring up some good points. Here's something that will help a little...
Just last week SmarterMail announced they will use contacts for Trusted Senders. See my request here:
Now when your customers with email clients sync their contacts, incoming messages from those contacts will be trusted. This doesn't solve everything, but it's a step in the right direction.
Kevin