Webmaster - DNS error al ingresar a mi sitio

Hola!
tengo un problema con un sitio hace un tiempo y no le veo solución, el hosting tampoco.
Resulta que desde ciertos dispositivos como celulares, pc, tablets (es aleatorio) el sitio aparece como no accesible y sale el mensaje:
"No se puede acceder a este sitio"
ERR_NAME_NOT_RESOLVED

Pasa usando 4g como wifi, en otro celular al lado de este otro si se ve el sitio, los dos celulares iguales.
Algunas veces me pasó en la PC de no verlo.
Tengo usuarios que todos los días me dicen por mail que el sitio tiene este problema y no lo ven, por las estadísticas veo que afecta al 50% de usuarios.

Es decir, no es un problema del dispositivo si no de algún estadio del hosting o DNS.
Ya me cambié de servidor dentro del hosting, me pase a otro hosting diferente y nada, sigue igual... probé cloudflare... nada.

Hice un nslookup desde el CMD de windows y sale la ip correcta del sitio.

Tengo otro sitio alojado en el mismo hosting y se ve perfecto, nunca tuvo este problema, además de muchos otros sitios que jamas pasaron por esto.

Este problema lo empecé a notar en diciembre pasado, y no fue que se hiciera algo especial, arrancó de un día para otro.

Espero alguien pueda ayudarme.
Gracias