I have had pretty good experience with hosting an email server on AlphaVPS, InceptionHosting and just now GreenCloudVPS.
GreenCloudVPS currently have a promotion until Sunday, and there are usually promotions around Black Friday on LowEndSpirit and LowEndTalk
I use them as IMAP storage for a few mailing lists I am subscribed to (but not for my main emails), but they do reject legitimate emails from time to time (not often, but it does happen - and those emails don’t show up in “Spam” or any logs).