beh, intanto prova a verificare se il tuo IP è finito in una di quelle liste tipo spamhaus (ad esempio qui: http://mxtoolbox.com/blacklists.aspx )
se il tuo IP è stato messo in qualche blacklist è a loro che eventualmente devi chiedere la rimozione