E é claro que descubro 6 minutos depois de postar a pergunta.
Você pode colocar permit_sasl_authenticated
em sua configuração smtpd_recipient_restrictions
e remover o smtpd_client_restrictions
ao mesmo tempo.
smtpd_sasl_auth_enable=yes
relay_domains=example.com
smtpd_recipient_restrictions=permit_auth_destination,
permit_sasl_authenticated,reject_unauth_destination
O fato de essa opção não estar documentada no link provou ser uma fonte de não quantidade insignificante de frustração neste caso.