DNS question

Ok…i have a problem recieving email from an outside company. I can send email from my establishment to their establishment, but am unable to recieve mail from them. They gave me their public IP address, which i can do a tracert to, a ping to, and a nslookup to…but yet…we are unable to recieve mail from them. Our company uses Exchange 2000 on Windows 2000 server…I personally think that somehow their config is messed up.Last i heard, they used NT 4.O server, but that shouldn’t matter should it??

Thanks 🙂