can’t find mail exchanger or IP address

I have a win2k AD domain setup. I’ve installed exchange 2k, sp3. I am able to send mail. However, if someone replies, they get an error message ‘can’t find mail exchanger or IP address’. I also have a yahoo account, and I also get the same error message if I try sending email to my account.

I’ve checked my DNS over, I do have an MX record there with the correct host name.

I’m also running behind a router, and I’ve checked that and it does allow both pop3 and smtp traffic in/out.
I’ve also have IIS running, and that is working fine, I’m able to access the website both inside and outside the network, so my domain is out there.

Any suggestions?