I use a subdomain with catch-all, like me.example.com. Everybody is fine with subdomains and then I can use companyname@me.example.com. Using that format doesn't expose my actual e-mail address and makes it easy to filter (if match companyname, immediately bin and never tell me).
For me, the actual email problem isn't huge - my first line of defense is giving out a burner email unless I want the primary site to be able to contact me. So I don't expect to get truly hammered with spam, and just want a way to know what happened if someone does sell the address.
The invalidation issue is a bigger one, and a subdomain is certainly a better solution for it. Disposable emails and the + notation are nice for people who either don't want to leave gmail, or are bound to it via college or company email system. They aren't the best cure, though.
Additionally you cannot send an email from foobar+dontspamme@gmail.com. If you aggressively use the + character for legitimate signups but need customer support they may not be able to find your account as easily (e.g. "we couldn't find an account associated with e-mail foobar@gmail.com").
Um. Why not?
[0] https://gmail.googleblog.com/2008/03/2-hidden-ways-to-get-mo...
The spreadsheet doesn't have to be that complex. Just treat the spaces between letters as bits. Dot is 1, no dot is 0. Suddenly, an e-mail temporal@example.com has 128 different variants, and your spreadsheet may just be a numbered list of companies :).
I have thought of a similar technique but this time using a period that would float between all the letters I have in my username. Any emails sent to an address without the period gets autodeleted.