Unable to receive on Exchange 2000

[BumRush]

I am setting up Exchange 2000 in a Win2k environment. I am able to send external e-mails and have that user receive them. The problem is that none of the internal users can receive e-mails from either internal users nor external users. When an external user tries to send an e-mail to us it gets bounced back with an e-mail from the postmaster saying:
"This is an automatically generated Delivery Status Notification.

Delivery to the following recipients failed.

"user@companydomain.com"

It also has the attachment saying:
Reporting-MTA: dns;server.companydomain.com
Received-From-MTA: dns;exch-connector.senderdomain.com
Arrival-Date: Wed, 27 Aug 2003 10:21:10 -0400

Final-Recipient: rfc822;user@companydomain.com
Action: failed
Status: 5.3.5
X-Display-Name: User Name

I have checked the MX record, made sure that the domain was set to "*" in internet message format, made sure that the SMTP virtual server is accepting all. It looks like the e-mail is being sent to the exchange server, but it's not reaching the intended recipient. Any ideas?

 

[BumRush]

When I use the nslookup command with set q=mx and then the company's domain it comes up with the ISP's information (primary name server, responsible mail addr, serial, etc.) Should I have the ISP configure the MX for our domain?
If I go on the exchange server, the smtp virtual server has a "badmail directory" setup and all my test messages both from external and internal address are sitting in there(D:\Program Files\Exchsrvr\Mailroot\vsi 1\BadMail). That tells me that the server is receiving the e-mails. But I still can't figure out why they are not being passed through to the correct mailboxes.