I just recently signed up for Infomaniak (www.infomaniak.com) which I believe meets all those requirements, although I can't speak for their uptime, because I haven't used it long enough.

It does let you use IMAP on the free account, which is what drew me to them.