It can be a new service not built on Twitter, say on identi.ca or friendfeed.
There'd be an API, so parties sending out emails can build into the service with a pre-established userbase.
Do you want to build it?
(afterward ... with relationships established with businesses.. can follow through into my idea http://bit.ly/1MscB3)
Given the amount of reaction this comment thread got, I'm considering hacking out a prototype and seeing if it helps alleviate the problem. That being said, I've already got far too much on my plate. I don't think you'd ever come up with this idea if you were the kind of person who had time to kill checking their notifications.
I'm possibly willing to spend $4000 on this, or something like it, which I'll build the front-end - depending on my work schedule.
The other side of the coin is information you'd like from firms, but are not getting, rather than vice versa - hence the friendfeed for business information.
(edit: the other aspect is having the end user be able to respond to some type of company information, in a type of Google Wave, so another response can be made)