Simply give them their company name as the username. I put fromamazon@mydomain.com and fromtesco@mydomain.com and then when an old account with deadcompany gets pwned, I redirect fromdeadcompany@mydomain.com to junk@mydomain.com with an alias.
I've yet to meet a company that's not ok with this. It's a bit embarrassing when you're talking to a human, but you'll get over it.