I do this all the time with Google Apps to track who sells my email address, creating a new one for each place I signup.
1. Create a catch-all address for the domain you're going to use that isn't the normal postmaster one.
2. Pick a three- or four-letter combination of letters that rarely appears in normal conversation (like dcj, for example).
3. Set a mail filter on the catch-all account to forward all mail that has your three-letter combination as a part of its recipient list to your real address.
This means that for every service you sign up for, you can create a new address (I always use domainname.code@mydomain) that is trackable and gets to you. For example, I just signed up with Via Rail's online system - using the address viarail.dcj@mydomain. It will get forwarded to my real address (since it's got the dcj in there), if I start getting spam on it I'll know where they got the email address from, and if it gets really bad I can just change my filters to block all email to viarail.dcj@mydomain.
You could do something with Gmail's plus-addressing, but I find that many services don't accept those email addresses.