I had similar problems and I went to the File menu in Outlook and opened a new Outlook data file and then went to the Data File settings and made it the default file. I then went to the iCloud client and checked the Mail, Contacts, etc box and it synced OK - which still downloaded bad email server addresses (the fix was to delete the prefix in the mail accounts so instead of p08.imap... they said .imap...
The downside is I now have my old messages in a 2nd personal folder file. I called the new Personal File Folder "Personal Folders 2013" to distinguish it. My rules (once I had 400 rules) won't work any more - but it's the best workaround I could come up with.