Indeed, there's definitely a market for such an email service. Then again who knows how much they'd be willing to pay for it. To have a manned service like that might be difficult to bootstrap.
Gmail can be free because it's a free service and you get what you pay for. To provide something of an equivalent service level for money with an additional guarantee of watchdog security services; you'd probably have to start around $10,000 USD per customer/year. And who's going to pay $10K for an email account?