Use a whole domain name, e.g. signup for dropbox with dropbox@tokenadult.com. You could do this with Google Apps Gmail by setting a catch-all forwarding address for the domain.
When an address is "compromised" and starts to receive spam, I move the line to a "banned_recipients" file with an SMTP reject header listing the new email. That way, a human using an old address would get a bounce back with the new email.
[1] so that the argument about bruteforcing "common-service@domainname" can be avoided
I'm running with this rule in the access map:
/^from-.*@foobar.com$/ OK
That accepts all mail to an address prefixed with "from-" and (by default) rejects everything else. This way you can just make up the dummy-addresses on the fly.I remember being slightly worried about using such a simple prefix when setting it up initially. However I have never received mail to a from-* address that I didn't "create". Not once in over 6 years.
And disabling an address that has turned spammy is as easy as:
/^from-stuffit-expander@foobar.com$/ 554 No thanks.