[PUL85]

Айм сорри, в администрировании я пока чайник, но могу предложить следующий расклад.
Т.к. вы перехали, возможно вы сменили провайдера, а если конкретнее - IP. Дак вот, для того чтобы ваша почта работала, провайдер должен распространять некую mx запись, там указан ваш IP... Может там запись неверная? (у провайдера). Взгляи-ните на DNSstuff.com, там есть *Email Test*, опробуйте... Быть может нет коннекта к Вашей почте вообще из вне? А к Вам почта приходит?

Exchange вроде-бы самому-то пофиг на IP...

Там в Эксчендже есть на вкладке Server->....->Queues, там поглазейте, почему задержки на отправку...

А быть может и на роутере у Вас прописан ваш старый IPшник