Se e-mails normais estiverem funcionando bem, mas os e-mails do sistema (como "Há atualizações X prontas para serem aplicadas") estiverem sendo marcados como spam, o problema é o conteúdo do e-mail e não externo fatores como a reputação do endereço IP, registros DNS reversos e SPF.
Eu vi o Gmail marcando muitos desses tipos de e-mails como spam e suspeito que deve haver algum tipo de atividade de spam ou phishing que corresponda a esses e-mails. Possivelmente servidores comprometidos enviando e-mails com um endereço De: de root@
.
Se você estiver usando o Google Apps for Business, poderá adicionar o endereço IP à lista de permissões, o que deverá resolver o problema. Você também pode adicionar um filtro ao Gmail para não marcar esses e-mails como spam, mesmo que você não esteja usando o Google Apps for Business.
Esses tipos de e-mails só devem ser encaminhados ao administrador do servidor, para que você não precise solicitar a todos os seus clientes a inclusão desses e-mails ou o endereço IP.