Qmail + speedy = mensagens não entregues

Pessoal,

Administro um servidor conectiva 10 + qmail, e nosso link é da telefônica. Speedy 600...
Não temos DNS reverso, pois a telefônica "desconhece" a informação de DNS reverso, não sabem nem o que é isso.
Muitos emails não são enviados, ficam retidos no queue do qmail, muitos por exemplo .ig.com.br, .unibanco.com.br, .aol.com, e mais um monte de domínios.
Outra coisa que ocorre, de alguns domínios externos você manda email para o domínio deste servidor e a mensagem é devolvida, informando "retry time not reached for any host after a long failure period", porém a mensagem retorna 1 minuto depois de enviada!!!!
O DNS está externo, sendo administrado pela locasite, e todas as conexões aparentam estar OK. Estou começando a desconfiar do link do speedy, por não ter DNS reverso e estar sempre cadastrado nas black lists da vida.
Alguém tem alguma idéia do que eu possa fazer?

Obrigado!