Spammers adding you to spamtraps?

I got asked a question at work today that had me stumped (although spf might be a solution).
The scenario:- The spammer create a spam email and spoofs the from email address. The From email address is set to be a spamtrap email address – one of the emails that will blacklist your domain if you send email to it.
The email then gets sent out to a million people – several of whom have out of office assistants turned on, and so they reply to say they are out of the office.
The result:- The spamtrap email address gets an email from your domain and your domain gets blacklisted. Your users can’t send emails to valid recipients and spamcop takes forever (12-24 hours on the best of days) to get your machine white listed again.

So my question is – how do you solve this problem or work around it? You need to keep out of office on so that genuine users will know if their email is going to get read or not. I was thinking that possibly spf would work. A user who is likely to check spamcop for blacklists is also likely to check spf records. If you have spf records set, then the spoofed email would not be accepted in the first place…… The only flaw with this is that it relies on both the relay machine AND the recipients to do spf checking – and not a lot of people do that.

I contacted 1&1 the other day to see if I could set up spf records for but they don’t support it on any of their packages – seems a shame, but also seems to be in keeping with their policy of not letting you getting your hands dirty in the real management of the network and making everything gui-ized.