As you deduced, Runbox and Fastmail are commercial services with fee structures. Fastmail was actually bought by Opera, but after a change in direction at Opera, is independent again. I think they are two of the better-known mail service which offered a number of options for users before GMail and various others.
I don't know what Xilo charges for hosting individual domains, as my account is as a reseller (NB definitely not
touting for business on TBB!) as it allows me to have a large number of domains of my own as well as hosting for clients too, at about a third of the cost (per domain) as you're paying.
POP/IMAP mail is available, but for many purposes, the spam filtering, mail searching, and storage for GB of mail, on offer from GMail, for free, give some advantages (not least in not having to concern myself with support of MS Outlook, among other things).
If you run a business, have a second ISP and backup web hosting...