Gmail Plus Addressing[0] is very similar to what you're suggesting.

[0]: http://webapps.stackexchange.com/a/2594

I think, spam is not the problem, email end-users are facing today. Filters are good enough.

People who want to register themselves to services with different email-addresses are likely to find a way to do so.

A bit like SpamGourmet [1].

[1] https://www.spamgourmet.com