Simple solution: give everyone address with "+suffix", and mark as junk any mail without it.
For stubborn services who don't accept "+" in email addresses use unique redirect aliases.
(Also, IIRC, Gmail ignores dots, i.e. "[email protected]" and "[email protected]" is the same address. Chose a canonical one with a dot somewhere, and filter the rest with exception for legimate senders.)
You can hide the + portion of a Gmail address behind redirects and forwards, if you feel so inclined. It's a lot of work, but it does let you use the "deliveredto" operator in Gmail to automatically sort and discard spam like that.
