Kan ikke modtage mails udefra på nye adresser

Heps

Jeg har et mystisk problem med vores EXCH2003-server, der består i følgende:
Mailboxene er sat op til at modtage mails fra 5 forskellige domæner og det har kørt perfekt indtil nu.
Men nu er jeg løbet i det problem, at når jeg opretter nye mailadresser på 2 af disse domæner, er det ikke muligt at sende mails udefra til dem - men jeg kan godt sende indefra (altså internt i organisationen)
Det gælder kun for nye adresser for disse 2 domæner - opretter jeg nye adresser for de 3 øvrige domæner, kan jeg godt modtage mails udefra.

Er der nogen, der har et bud på, hvad det kan være?
Jeg har tjekket alt igennem og kan ikke finde noget, der skulle blokere for noget.