Parece válido. Tente especificar o endereço IP, embora isso tire um nível de possível falha.
v=spf1 a mx ip4:213.133.103.5 ~all
EDITAR
Eu vou esclarecer. Eu não estou dizendo que isso deveria ser uma solução permanente. Isso é suficiente para fazer as coisas funcionarem (e o fluxo de e-mails) até que o problema real possa ser encontrado.