That's interesting to me. What service do you use that lets you quickly generate new addresses? Or are you running your own server?
I also use a separate email alias for each company I deal with. I run my own Postfix servers (primary + backup), but I've now created a web UI with a view to making this usable by others. The URL is in my profile (not sure if posting it here would be considered spam). It's still early days, but seems to work fine for my own emails. If you'd like to use it I'll be happy to create a (free) account for you.
Nice thing about this system is that I can immediately tell where spammers got my email address and shut it off. Also, any email that comes in that doesn't contain a SECRETKEY gets ignored, so I don't have to worry about spammers sending to [email protected] and [email protected].