Я сразу по существу на примере себя опишу. Ситуация примерно схожая. Т.е., хостинг, клиент с корп. почтой и парочка сайтов.
Поначалу я тоже пользовался бесплатными ДНС. Потом чет начались глюки, у них чет перестала работать синхронизация и т.д.
В итоге:
Купил VDS у айхора, 200 руров в месяц. На нём поставил ISPConfig3, утащил туда все свои сайты, и все домены отправил хоститься туда, как и почту.
Купил второй VDS на фирстВДС (не плеваться!), самый дешманский, тогда он стоил 60 руров. Сейчас 90 уже. На нём только ДНС стоит, так что, ресурсов выше крыши.
Первый ВДС стоит как главный, там хостинг доменов и всё остальное, при изменении записей в домене, об этом сразу извещается вторичный ДНС сервер. Всё, глюки кончились.
Существенный плюс - делай, что хочешь. К примеру, я замутил свой сервис ДинДНС. Что интересно, всё работает.