O Outlook 2007 inclui uma regra somente de cliente padrão chamada "Limpar categorias no email", que é aplicada ao email de entrada. Se os destinatários também estiverem executando o Outlook 2007, eles nunca verão suas categorias de saída depois que o Outlook as filtrar no lado de entrada.
EDIT: Existem duas regras na minha instalação, uma para cliente somente (.pst) e uma rotulada sem a tag "somente cliente", presumivelmente para contas IMAPI.
EDIT2: para dar uma olhada, Tools | Rules and Alerts...