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.
Why do you need to put faith in them? Switching email providers is just a DNS change away, and email messages can be stored locally - actually it's encouraged to do so.
You do have a point. But I still do not feel comfortable. Besides I can't envisage changing providers whenever I face trouble and it gets unresolved in a timely manner which is what I assume in the current setup. Pinboard is another example. Anyway, it kind of doesn't work for me.
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.
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.