Sim, você precisa criar uma segunda regra "Aplicar regra nas mensagens que eu enviar" .
Além disso, se você precisar manter categorias para mensagens enviadas, será necessário ativar o suporte para isso no Outlook e no Exchange Server.
No Outlook 2003+, você precisa editar o registro da seguinte maneira:
HKEY_CURRENT_USER\Software\Policies\Microsoft\Office\XX.0\Outlook\Preferences
DWORD: SendPersonalCategories = 1
Em que XX é o número da versão do Outlook (de 10 para o Outlook 2003 para 15 para o Outlook 2013).
No Exchange Server 2007+, você precisa executar o seguinte comando do PowerShell:
Set-TransportConfig -ClearCategories $False
Isso impedirá a eliminação de categorias nas mensagens enviadas.