Я бы в первую очередь заустил traceroute и посмотрел куда и как идут пакеты в сетях Билайн до DNS. Ещё проверьте приоритеты DNS серверов. На первом месте должны быть от Билайн. Вариант лучше - через Wireshark посмотреть как происходит получение ip адресов по DNS: что ушло, что пришло в ответ, как и в каком порядке.