Exchange mívá své vrtochy. Většinou ale bývá problém v konfiguraci nebo HW problému (problém s nekvalitním připojením například).

Nejprve si přečti nísledující KBčko a zkus ověřit zda vůbec a případně ve které frontě ti to zamrzá (případně jde-li mail "odmrznout" pomocí tam popsaného postupu bez nutnosti restartu služby:

http://support.microsoft.com/kb/823489

Podle toho pak můžeš hledat dál (kdyby sis nevěděl rady, můžu se pokusit pomoci, ale je potřeba, abys problém blíže specifikoval)