Ona greška sa sertifikatom nije krucijalna, onodsno server će funkcionisati ali nećeš moći koristiti TLS za komunikaciju. E sad, ako ti je TLS jedini dozvoljeni protokol, onda si našao razlog za tvoj problem. Inače, self-signed sertifikat je sasvim dovoljan za ovakvu operaciju, i već uz Exchange dobiješ jedan takav, verovatno si ga ti obrisao ili nisi konfigurisao sve kako treba pa zato dobijaš grešku. Naravno da je bolje kad ti sertifikat izda odnosno overi neki autoritet, ali može i ovako da prođe.
Onaj NDR koji si dobio nakon brisanja poruke je trenutno bezvredan, jer ti ta greška kaže da poruka nije ni stigla do udaljenog servera jer ju je administrator obrisao (odnosno, kaže ti "pa sam si obrisao poruku, i šta sad hoćeš više od mene" :-) ). Proverio sam ti i domen, nisi na blacklistama, pa to nije razlog zbog čega poruke nisu otišle. Hotmail, Yahoo, Gmail i slični imaju i greylisting varijantu, gde svaku poruku sa novog domena najpre stave u greylistu, i traže da bude poslata ponovo. Spameri to uglavnom ne rade, i ako u roku od n minuta ne stigne ponovo zahtev za slanjem, domen automatski biva stavljen na blacklistu. Pošto se admini normalnih domena trde da ne ulete na black liste, oni obično i pošalju poruku ponovo, i na taj način budu automatski stavljeni na white listu. Međutim, koliko se sećam, od njih dobiješ i NDR u kojm nešto slično i piše.
Po meni, najbolje je da uključiš kreiranje logova na SMTP konektorima, i ispratiš šta se dešava sa tvojom porukom na odlaznom konektoru. Uputstvo za uključivanje logova i njihove lokacije možeš pronaći na:
http://exchangepedia.com/2007/...ng-smtp-protocol-activity.html
(isti je postupak i za 2010, ne daj da te naslov iz linka zbuni)