Para as interfaces web, os usuários só precisam de um proxy HTTP para enviar e-mails, então seria impossível bloquear sites específicos sem inspeção de tráfego.
Além disso, a inspeção do tráfego HTTPS requer a execução de algum tipo de MiTM - a instalação em máquinas do usuário da CA raiz e a assinatura do certificado curinga para o servidor proxy [transparente], que descriptografará e analisará todos os dados HTTPS transmitidos.
A maneira mais simples de impedir que usuários inexperientes usem serviços de email externos pode ser o bloqueio de DNS - instale o servidor de cache DNS em sua rede, limite solicitações externas em portas UDP e TCP 53 para que apenas esse servidor possa fazer isso e adicionar registros DNS para domínios indesejados que apontam para algum outro IP, ou seja, 127.0.0.1
Esse tipo de bloqueio pode ser contornado com facilidade. É muito melhor fornecer serviço de correio interno e persuadir todos a usá-lo apenas para cartas de trabalho.