Se estiver sendo bloqueado devido a um registro SPF, o ideal é que eles corrijam seus registros SPF para incluir os hosts MX de envio.
O motivo pelo qual ele será bloqueado por seus servidores de e-mail e não por outros é simplesmente a configuração de servidores de e-mail ou retransmissões em sua organização para honrar os registros SPF do remetente. Outras organizações optaram por não honrar o SPF.
Se eu estiver na mesma posição que você, eu normalmente colocaria o remetente na lista de permissões temporariamente (se isso for possível no seu servidor de e-mail / retransmissão de e-mails / filtros de spam), evitando a verificação do SPF, se necessário, e incentivando-os a alterar seus registros SPF.