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. "j.random.user@gmail.com" and "j.r.a.n.d.o.m.u.s.e.r@gmail.com" is the same address. Chose a canonical one with a dot somewhere, and filter the rest with exception for legimate senders.)

you can get the same effect with arbitrary dots.

e.g. first.last@gmail.com is the same as firstlast@gmail.com

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.