I guess one part of the problem is deciding on a flat-fee for a year, or a price which is dependent upon the number of accounts/users you have.

Were it me I'd rent a VPS and configure email myself. A less technical user might find that too much work (although online control panels might make it more palatable).

A decent VPS might cost $20/month or $100/year and would be sufficient to handle mail for 50ish users.

Sure a VPS just for email might seem like overkill..