Cześć,
Zmiana na jakiś inny serwer DNS u Twoich klientów to nie jest rozwiązanie.
Problemem nie są DNS klientów czy ISP, a problem z TTL na Twojego wpisu w serwerze DNS Twojego hostingu.
Przykład masz ustawiony TTL swojej domeny na 3 dni i pod adresem 192.168.0.1 jest Twoja domena halotelefonek.pl.
Ja jako użytkownik wpisuje adres do przeglądarki. Następnie mój komputer wysyła pakiet z zapytaniem DNS do serwera DNS który ma uzyskany od serwera DHCP na moim routerze. Mój router na porcie WAN ma skonfigurowany serwer DNS mojego ISP (po DHCP, PPPoE, statycznie) i teraz serwer DNS dostawcy sprawdza czy ma taki adres u siebie w cache jeśli ma super wraca odpowiedź i pokazuje się strona.
Jeśli nie to serwer DNS dostawcy, wysyła zapytanie do root-serwerów które informują go, że domenami ".pl" zajmuje się NASK (w przypadku polski), a NASK te informacje uzyskuje już od serwera DNS Twojego hostingu. Informacja ta zapisywana jest w cache serwera DNS Twojego ISP oraz na krótko na Twoim routerze w celu szybszego ładowania.
Teraz skąd rodzi się problem. Przy długim czasie życia (TTL) np. 3 dni. Ja dzisiaj zapiszę stronę do cache DNS mojego ISP, a Twój hosting zmieni adres z jakiegoś takiego czy innego powodu. I przez 3 dni, do czasu wygaśnięcia tego wpisu na serwerze ISP Twojego dostawcy. Za to inny klient z drugiego końca polski, odpyta po awarii i uzyska poprawny adres. Jeszcze inny klient ma DNSy googla sławne ósemki (8.8.8.8) i też strona mu się załaduje.
Oczywiście powodem dla którego niektórym klientom strona nie działa, może też być problem po ich stronie, chwilowe zawieszenie się serwera DNS, jakieś wirusy, robaki, problem z serwerem DNS u ISP.
Proponuje zacząć od dokładnego sprawdzenia konfiguracji domeny na Twoim hostingu i kontakt z pomocą techniczną, a następnie odwiedzenia kilku linków z google "jak działają serwery dns".
Pozdrawiam.