Other companies already do that. Many of them. In fact, at the risk of sounding like self-promotion, that's our primary business, though we're small fish in the field.
There's definately a market for it, both B2B and B2C. Mailservers are some of the most annoying things in the world to setup and maintain, and a lot of people would rather pay someone to do it than deal with the hassle themselves. It's a hard thing to advertise, though - there are only so many things you can offer to "out-spec" your competitors.
Billing can be a hassle, if you're trying to charge for bandwith used, figuring out who sent what...
And, yes, watch out for spammers. We do some pretty exhaustive checking on prospective customers to determine whether they're legit or not. It's very easy to get burnt.