Bem depois de um monte de pancadas, eu descobri isso sozinho. Primeiramente, há um bug em algumas versões do rsyslog que impedirão que isso funcione (você nunca verá uma conexão estabelecida para um ou mais dos servidores de destino), portanto, verifique se está usando a versão 7.6 ou posterior do rsyslog.
Verifique se o seu arquivo de autoridade de certificação possui alguma autoridade de certificação necessária para todos os destinos listados nela. Ordem não é importante. Então o seu arquivo conf deve ser parecido com isto:
$DefaultNetstreamDriverCAFile /etc/pki/rsyslog/ca.pem
*.* action(type="omfwd" protocol="tcp" Target="10.50.59.241" Port="6514" StreamDriverMode="1" StreamDriver="gtls" StreamDriverAuthMode="anon")
*.* action(type="omfwd" Protocol="tcp" Target="some.other.host.com" Port="6514" StreamDriverMode="1" StreamDriver="gtls" StreamDriverAuthMode="x509/name" StreamDriverPermittedPeers="*.some.other.host.com")