Not resolving domain?

I have a user who can’t get email to deliver to someone. She gets an NDR that says “The recipient was unavailable to take delivery of the message… Host unreachable”

Someone at the place she’s sending to said “The problem is with their mail relay, it is not resolving the State’s domain name.” It is an @state.de.us email address.

We have Exchange 5.5 running on a Win2K server. How do I go about figuring out why it is “not resolving the domain name”, and fixing it? Thanks!