[cameron]

События DNS выдают ошибку 4004, 4007, 4015. »

это очень информативно, ведь коды ошибок системные администраторы знают наизусть.

Какие данные нужны предоставить для помощи? »

судя по всему, ваш DNS сервер закешировал данные об адресе вашего почтового сервера.
чтобы убедиться в этом посмотрите вывод
nslookup mail.имя_сервера_com.ua с этого вашего сервера DNS
и с ПК, у которого установлен гугло-ДНС.
Если циферки-IP адреса будут разные - то в консоли DNS сервера очистите кэш, проверьте после этого.
а на клиентах, для очистки кеша можно использовать ipconfig /flushdns