Earlier quoted context omitted.
My suggestion would be to try Purelymail. They don't offer much in the way of a web interface to email, but if you bring your own client, it's a very good provider. I'm paying something like $10 per year for multiple domains with multiple email addresses (though with little traffic). I've been using them for about 5 years and I had absolutely no issues.
Pricing it hard to understand: https://purelymail.com/advancedpricing Usernames on shared domains: 1 to 6 letters: $0.20 per user per year 7 to 12 letters: $0.05 per user per year 13+ letters: $0.02 per user per year WTF?
Personally I use the simple pricing scheme and looking at billing page, I pay around ~$0.35-0.4 monthly for 5 domains, with 4 explicitly set email addresses and catch-all for all domains to a common mailbox. Also I must state again, there is quite little traffic on all.