Way to import email from the raw email files

You should be able to copy your messages from outlook data file to IMAP server. I've done it many times, but mostly data file -> Exchange Server.

First of all think about do you really need to transfer old email to a new server. You can delete your old account and simply open the data file in Outlook to have an archive of the old emails. If you need them to sync to another device, then keep reading.

First you need to locate the data file that contains your old messages. You can do so by going into account setup and there will be a tab called data files. In there you can figure out which data file is the one that holds old mail. There should be a button to open file location.

Next copy it in a safe place so you can open it in case you mess something up (you have to close Outlook first).

Then you can delete the old account so it stops bugging you while you keep working form account settings. Your old mail should remain open after you delete the account, but if it goes away you can do File -> Open outlook data file (or File -> Import for older versions and follow the wizard).

If your IMAP account is not setup, do so now.

You should now have two email accounts and you can drag and drop mail between them.

Some advice:

1. Backup your IMAP mail before you begin.
2. I suggest you create a folder for your old mail on the IMAP server, something like "archive", you can move it to Inbox later if you wish
3. Do not under any circumstances copy all of your messages at once! It will crash and burn!
4. Locate your oldest message in old mail and create search folder to filter messages starting from the oldest date for the next week or month, depending on how many messages you have. Never go more than 500 at a time with 6GB RAM, but if you have attachments bigger than 5MB, go even less - say 300
5. Write down how many emails there are in the search folder
6. Copy messages from the search folder to your IMAP folder
7. When it's done check how many messages are there in your IMAP folder and see if it matches what you have in the search folder
8. Modify the search folder for the next date range (say if it was 1.Jan 2013 - 15.Jan 2013 move it to 16. Jan 2013 - 1. Feb 2013.)
9. Take a note how many emails are in your new date range
10. Copy them to IMAP server and check how many are there, it should be the SUM of numbers you have written down
11. If it matches repeat, if not you can create search folder for your IMAP account to narrow down where the problem was. Some messages are stubborn and will have to be copied individually

That is about everything I can think of right now, but if you run into a problem let me know, and I'll see what can I do to help.

You will probably have some problems, this never ever, ever goes smoothly but it's the simplest way to get it done.

After considerable research, today I answer myself: YES, it IS a hosting provider issue. Here are the reasons:

Today, SPF alone is not enough anymore to validate a sender for any serious email provider. Because of email-deliverability, more and more businesses rely on third-parties especially for newsletters, but not only: my office environment might rely on a cloud provider to enhance workflows, including emails, which will only rarely correspond with the domain hosting provider.

Consider that I might send my newsletters through someprovider.com. So I need to insert someproviders SPF space into my SPF record. But someprovider might be hosted by somecloudservice and have shifting IP addresses. In that case, someproviders SPF record might actually include the full address space of somecloudservice. This means that anybody else hosted not only on someprovider, but even on somecloudservice could spoof my emails, and SPF validation would still work!

That is one reason why gmail and other services will clearly indicate you that the email you received was sent through a third party (See google support documentation). For the same reason, Outlook / office 365 could flag such email as SPOOF (see here: microsoft office 365 documentation).

Only a valid DKIM signature can certify the actual sender of an email. That is why DKIM was created in the first place (Details: Wikipedia article - DKIM.org official website).

Since spoofing and phishing is an ever-growing issue, anybody should have the instruments to know who was the sender of a given email. This is why I strongly propose that any serious hosting provider should not only implement DKIM, but possibly activate it by default.

Also, I am quite sure that big email providers like the ones mentioned above, will soon start to penalize any emails which are not DKIM signed, especially since it has become an official internet standard already in 2011 (see Wikipedia article above). Spam & spoof are still a growing problem, and there will be a growing tendency to filter out any email which is not clearly legitimated.

So, we have changed our email provider, as without DKIM we have a smaller and smaller chance of our emails (not only newsletters, but daily business emails) reaching the inbox of the intended recipent.

EDIT:
Six months after having transitioned to our new email provider, I can confirm that the consequent implementation and use of DKIM has resolved ALL of our previous delivery issues.