Зависит от того, как у вас сконфигурирован Exchange, но можно сделать так: включить домен, который вы используете External Relay и создать Send-Connector, который будет пересылать почту на сервер хостера. Записи MX должны смотреть на сервер Exchange.
Таким образом вся входящая почта будет попадать на Ех, он будет проверять локальную базу и если пользователя там нет, отправлять письмо на сервер хостера.
P.S Увидел, что решение уже предложили. На стороне хостера надо создать заглушки для всех ящиков которые находятся в эксчейндж сервере. Заглушка - это простой форвард на мэйл из другого домена (без него к сожалению никак). Т.е на эксчейндж добавляете домен - мойдомен2.ру и каждому пользователю пишете дополнительный мейл с этим доменом. На стороне хостера создаете форвард вида вася@мойдомен.ру -> вася@мойдомен2.ру, где вася@мойдомен2.ру это то, что вы прописали пользователю в эксчейндже.
Ну или таки разошлите всем инструкцию, как переделать себе профиль на новый сервер...