How would you provide a 554 rejection notice for spam?

I've recently put SpamAssassin in front of my Exchange server as an SMTP proxy.  Our previous spam filter would provide a 554 rejection notice for anything that was identified as spam.  This meant that any FP would be notified so that email would not get silently ignored.  Although a rejection notice was sent, we still retained the spam.  This meant that when our users got a call from their customer about the rejected spam, they could quickly locate the message without it having to be resent.

I would like to continue doing this with the new SA/Exchange setup.  Right now I use spampd but I would like to change to Sendmail just because it is part of the default install for Redhat.

How would you go about providing a 554 rejection notice?  Would you do it on the SMTP proxy?  On Exchange?  Would you use Sendmail?  Postfix?  Something else?