Распространение вашей измененной записи DNS в Интернет занимает время. Новая запись будет автоматически заменена, когда срок вашей старой записи истечет, как определено в TTL. Вам нужно подождать, пока истечет TTL.
Проблема была очень глупой и очевидной: у моего хостера был активен блок UDP на машине.
Я предполагаю, что Mac и Android используют резервный DNS-сервер на случай, если он недоступен? Это объяснило бы неправильные (правильные) результаты.
Однако на Linux-машине nslookup / dig с использованием нового DNS-сервера приводил к тайм-ауту.