My tiny hosting company Varialhosting offers POP and Imap. I did a quick search and there are tons of providers that offer Imap.
They have treated me well, I have not noticed any downtime, but I am not very sensitive to that.
They also allow virtual domains, so I have three websites, two very low traffic, for the price of one.