Hola,
La única forma de comprobar si el problema está en level3 y telefónica es que accedas a tu servidor por SSH y hagas una traza a una ip de telefónica de algún cliente que se te haya quejado. Copia este comando sustituyendo IPTELEFÓNICA por la ip de tu cliente:
o si tienes instalado 'mtr' que es más 'visual':
Si la traza se queda en los routers de level3 es que ellos seguramente tienen razón, aunque yo si fuera Hostdime cambiaría la ruta por otro proveedor diferente a level3 y asunto arreglado. Si no lo hacen es porque te habrás quejado tú sólo y no les compensa el rato de trabajo del operador de redes y el volumen de tráfico enrutado.
Yo te recomiendo que te cojas un servidor en Hetzner, le añadas la opción de Cpanel y que una empresa autónoma te lo administre, te saldrá más barato y tendrás una opinión cualificada siempre independiente del proveedor: http://www.hetzner.de/en/hosting/produktmatrix/rootserver-produktmatrix-ex . Te digo Hetzner porque hoy en día es uno de los pocos proveedores que para mi están dando la talla en la gama baja-media, pero puede ser cualquiera.
Yo he hecho trazas desde Hetzner a Telefónica y va por Globalcrossing la ida, por lo que no tendrías en principio el problema que tienes con level3.
Un saludo.