Instead of selling your customers on postfix being easy for relay, sell them on mail accounts that are super secure (apply snake oil as needed)
We recently took on the mail domain for a DSL company that allowed its 5000+ customers to mail unauthenticated so long as the IP space was within the DSL range.
That was a nightmare and we forced everyone to authentication and "sold them" (at no real cost) on the extra security and additional features within Smartermail.
It cleared up 99% of the spamming and blacklisting issues and many thanked us for making it easy for them to easily self-help to change their settings using our KB.
This also included secure password changes that were just outright horrendous.