http://support.microsoft.com/default.aspx?pr=exch2k
http://www.techtutorials.info/exchsetup.html
http://www.swinc.com/resources/exchange/smtp.asp
a ještě česky pro Exhc2003: http://www.microsoft.com/cze/servers/exchange/techi nfo/
Obecně bývá problém s relayingem, defaultně je tuším úplně vypnutý až na localhost (schválně si zkus poslat mail přímo ze serveru, klidně jen telnetem na port 25). Exchange neuznávám za kvalitní MTA, tudíž se mu věnuji jen velmi okrajově.
Nicméně by bylo vhodné uvést, kterou verzi se snažíš zprovoznit.