Nos consiederan SPAM sin ser Spammers

Tenemos venta online, y los correos con el pedido se generan de forma automática, adjuntando una factura en PDF con el número de pedido. Llega sin problemas a todos los dominios, exepto a @gmail, donde nos devuelve siempre el siguiente mensaje:

Hi. This is the qmail-send program at vps75078.ovh.net.
I'm afraid I wasn't able to deliver your message to the following addresses.
This is a permanent error; I've given up. Sorry it didn't work out.

<usuario @gmail.com>:
2a00: 1450: 400c: 0c05: 0000: 0000: 0000: 001b failed after I sent the message.
Remote host said: 550-5.7.1 [2001:41d0:52:700::697 12] Our system has detected that this
550-5.7.1 message is likely unsolicited mail. To reduce the amount of spam sent
550-5.7.1 to Gmail, this message has been blocked. Please visit
550-5.7.1 http://support.google.com/mail/bin/answer.py?hl=en&answer=188131 for
550 5.7.1 more information. Ed9si3491192wib.29 - gsmtp

--- Below this line is a copy of the message.
Para nada hacemos SPAM y la media de envíio de emails es de 25-30. Sin problemas con yahoo o hotmail, etc, pero no llegan a @gmail

Hemos mirado y no estamos en ninguna lista negra, ni el dominio, ni la IP. Hemos contactado con @gmail, pero no obtenemos respuesta.