It seems that the nice people at Microsoft were looking out for us, lest the evil people in the world see how we categorise our email, and decided to strip away any category information from sent and received objects by default. Sure, I understand if you were categorising emails from someone as "sneaky git" or "numbnuts" then you might not be too happy about sending those out…but really it should be your choice right?
Did you know, for example, that In your Outlook 2007 rules there is a sneaky little enabled by default rule that clears the categories?
Removing that is an obvious first step!
The next step involves editing the registry, so make sure you know what you are doing before editing, always back the registry up first
There are also some registry keys you'll need to add, so open up Regedit and in HKCU\Software\Policies\Microsoft\Office\12.0\Outlook\Preferences, create DWORD keys SendPersonalCategories and AcceptCategories with values of 1. You'll need to restart Outlook for them to apply.
Finally, as per this TechNet article, log on to your Exchange server as an Exchange Organisation Administrator and run the following command in the Exchange Management Shell
Set-TransportConfig -ClearCategories $False
You should be able to send and receive emails, appointments, tasks and any other Exchange object that supports categories, complete with category intact.