Kriz, there are many fairly stable providers out there with IMAP support. Typically any provider running on linux (and most on windows) will have IMAP. I'd suggest looking for a provider using one of the following panels: cpanel, DirectAdmin, Plesk, or Hsphere (helm for Windows I believe has IMAP bundled in as well). Naturally be sure you do some research on the provider before just signing up with anyone blindfolded (as there are many hosts coming and going nearly all the time).
Best of luck in your search