Т.к. у яндекса для pop3 & smtp используются разные сервисы - то обычным CNAME в DNS не обойтись (т.е. можно, но их нужно 2, на один все повесить не выйдет), но можно настроить простейший роутер внутри сети, можно использовать виртуальную машину линукс (или текущий дефолтный шлюз, если он позволяет), которая делает всего два действия:
слушает порт 25 в локальной сети -> форвардит все запросы на smtp.yandex.ru:25 (IP - адрес само собой_
слушает порт 110 в локальной сети -> форвардит все запросы на pop.yandex.ru:110
а на саму машину CNAME как mail.domain.ru
Думаю это самый простой способ, что б не обходить кучу машин.