One possibility is to have your spamfilter bounce all messages that seem like spam, with instructions to re-send the message with a specific tag in the subject (e.g. "NOT-SPAM").
Actual spammers don't look at their bounces, but legitimate e-mailers would get the bounce message and re-send their message with the tag. If you wanted to get particularly fancy, you could have anyone who had ever re-sent an erroneously bounced message to a whitelist, so they'd only have to go through the process one time.