Some of the best help with front line spam prevention is the reputation services, decision making based on current Sender Score or Trusted Source.
Since you don't have that, maybe you can try Google Apps for the customers that want better spam protection and possibly other features?
I can give you a coupon code, or a code for each of your customers, depending if you host and bill them all for service from an account you manage, or you make each of them signup and they get billed directly and then you'd help support their individual accounts.
As for the Plesk, does it still have an /etc/mail/spamassassin/local.cf that you can edit and won't get overwritten? That would allow you to apply a global blacklist based on From: addresses.
Plesk may also support the ability for a per user .spamassassin config that you can edit within each users Maildir structure.
You can also try enabling some RBL's with rbldnsd that are applied to all incoming emails such as using the Spamhaus RBL.