[Cork]

DLC, I can only contribute based on the little I know. Here are some thoughts, but take this with a grain of salt. With luck, someone with more knowledge will see this.

1. My experience with Outlook is that it will do an excellent job of picking up info from other MS mail programs. I've converted from Vista's Mail but not to Outlook, but I'd be shocked if Outlook could not capture Categories from Mail when it captured them from my Palm Desktop. This part should work fine.
2. As for syncing with the Windows Mobile device, I suspect your options will be to sync Contacts or not. Here I could be wrong, but I do not believe you can sync a portion of your Contacts. Suggest you check on a MS Outlook-specific forum in the Office or Windows communities.

Good Luck!