The one thing you'd need to make sure of when implementing this would be to make rejection/acceptance happen at SMTP time. This goes especially for the notifications about a new email address, don't generate a new mail for these but rather give the information in an SMTP error message. Otherwise you're just aggravating the situation, because bounces and automatic messages in reaction to spam are almost as much of a problem as the spam itself these days.

All in all I'm not overly optimistic about the efficiency of this scheme. There is a lot of evidence of cooperation between spammers and virus writers, and it'd be trivial to write a virus which, additionally to just sending itself out to everyone in a victims address book, harvests this address book and sends it back to the spammer, complete with the victims address. Then the spammer has a set of sender-recipient addresses which are guaranteed to work (unless there's an additional anti-spam-mechanism in place) for segmail addresses. Sure, you can then rotate the address, and the spammer can harvest it again, lather, rinse, repeat. It's an automatic process for the spammer, not so automatic (and rather tortuous) process for you. For this to happen segmail would have to become popular enough to register on the spammers annoyometer first of course, so I guess it can be useful until then (sorta like grey-listing).

Personally, the annoyance of my correspondents having to keep track of which address is my current valid one (and valid for them, not someone else) would keep me from using such a scheme. I'm quite happy with my anti-spam setup at the moment (in fact, I receive far more spam via snail-mail than email, wish someone would implement Spamassassin::RealWorld ;-).