Your wish will be granted in Outlook 2007, which will store categories in the user's default store. Check out Hank's blog entry for some preview information on color categories -- http://blogs.msdn.com/melissamacbeth/archive/2006/02/17/534491.aspx

Signature
Sue Mosher, Outlook MVP
Author of Configuring Microsoft Outlook 2003
http://www.turtleflock.com/olconfig/index.htm
and Microsoft Outlook Programming - Jumpstart for
Administrators, Power Users, and Developers
http://www.outlookcode.com/jumpstart.aspx
> Just about everything in Outlook is central to Exchange when set up on a
> domain, but I've found that Contact Categories are only stored in a registry
> key. If a user has set up their own categories and then logs into a
> different computer, their categories are not available. They key has to be
> exported/imported. The categories should be stored in Exchange so that they
> can be accessed and updated from any computer.