It's not an issue with the host. You need to backup your emails off of the server (either archive or switch your email account to POP) then you now have all your email stored locally rather then on the server (which is what IMAP does). Then switch over to the new server and if you want to move your old emails onto your new server most email clients will allow you to just drag and drop emails into the folders. However, if you have many emails I'd suggest going through them and deleting what you can before even starting this process. If you have several gigs of emails to backup you'll want to download them over night. If your host doesn't offer a simple backup option that's compatible with your new server then this is your only option. There may be some programs that will do this for you but it's essentially the same thing.
Migrating from a WHM/cPanel system to another host with the same setup is usually very easy, KH will even assist with the migration, but if it's anything else the above is what you're going to have to do.