Primero tines que hacer un traceroute desde tu server a tu conexión y viceversa.
Guarda los resultados por que los necesitarás.
Con eso podrás saber donde está el bloqueo del IP de tu server, posibles opciones:
1- El problemas es que tu server no sale de theplanet, abre un ticket y pide que comprueben ese problema (a veces los ip se pierden por un error...)
2- El problema es de la parte de TDP en Lima, paciencia y tienes que conseguir llegar al departamento de redes de telefónica, encontrar alguien que te entienda, explicárselo y entonces verán tu problema y lo solucionarán, pero ten en cuenta que debes de pedir que te pasen con un supervisor por que "es un problema de red", debes de ser "firme e insistente".
3- Los DNS de tu server están bloqueando los DNS de telefónica (Raro)
4- Si la cosa te corre prisa porque por lo que dices tus clientes están en el aire, tendrás que contratar a alguien que analice tu broblema y te de una solución.
Nota: Si llevas dos dias y no eres capaz de solucionar un problema así, teniendo a tus clientes colgados por eso, quiere decir que no estás capacitado para usar servidores no manejados debes de abrir los ojos y asumir que tienes que contratar servidores manejados o un mejor proveedor si tienes una cuenta de reseller.
En internet obtienes exactamente lo que pagas...