Eu descobri!
Eu precisava adicionar um registro SPF TXT às minhas configurações de DNS. As máquinas que puderam usar o SSL para enviar para smtp.gmail.com estavam funcionando bem porque não exigem o registro. No entanto, qualquer uma das impressoras que não permitiam SSL precisava desse registro para se conectar com aspmx.l.google.com.
Inicialmente, achei que o registro já existia porque alguns deles estão funcionando, mas após uma inspeção mais detalhada, eu estava incorreto.
Para referência: Para criar um registro SPF para um domínio: Criando registros SPF do Google
Log in to the administrative console for your domain. Locate the page from which you can update the DNS records. You may need to enable advanced settings. Create a TXT record containing this text: v=spf1 include:_spf.google.com ~all
Publishing an SPF record that uses -all instead of ~all may result in delivery problems. See Google IP address ranges for details about the addresses for the Google Apps mail servers. If your registrar also requires a host setting (such as @), see the TXT records for specific domain providers list for precise instructions. Save your changes. Keep in mind that changes to DNS records may take up to 48 hours to propagate throughout the Internet. If you have difficulty creating an SPF record, contact your domain provider for assistance.