Even just setting START TLS REQUIRED might solve your spam problem, as long as only a tiny minority of people did it. That would have the added benefit of protecting you from Yahoo Mail users, the FBI, and such.
At this point, I'd consider NOT using START TLS for your MTA to be nearly as irresponsible as not using ssh instead of telnet/rsh, or not using secure passwords. It correctly pushes all the pain onto the sysadmin (and a very tiny amount of pain), rather than end users.
Do you know if a successful response to a START TLS command endured end-to-end TLS secured mail transport?
I kinda doubt it - if for some reason your outgoing mail server connects to one of my secondary/relaying MX servers, I don't think there's any way for you to ensure that server bothers trying to set up a TLS session when it relays my mail(which I guess is mostly my problem/fault) - and similarly, if your ISP requires you to send mail via their SMTP servers (blocking port 25 isn't uncommon here) - I don't think you've got any say in whether or not that server requires TLS?
(I know - I really should go and look this up myself…)
Usually people do not block 465 or 587 (if they do, they really really suck, and you need to VPN through that network anyway). For outgoing mail, you just do STARTTLS directly to your own smarthost over those ports.
At this point, I'd consider NOT using START TLS for your MTA to be nearly as irresponsible as not using ssh instead of telnet/rsh, or not using secure passwords. It correctly pushes all the pain onto the sysadmin (and a very tiny amount of pain), rather than end users.