Nadie va a responder a kapachov?
Los servidores de correo no disponen de caché propio, usan el revolver del sistema. Por lo que si hay algún problema con el caché es porque el sistema esta cacheando... no el servidor de correo en sí.
Pon el valor de TTL de tus zonas en 5 minutos o incluso menos, si el servidor no esta excesivamente cargado no supondria una carga excesiva.
También se me ocurre que podrías usar los servicios de empresas como UltraDNS que te aseguran el 100% disponibilidad:
http://www.ultradns.com/services/mdns.html
Un saludo