Mail is getting stuck in the IMS Queue

We have Windows NT 4.0 with SP 6. We use Outlook 2000 and Microsoft Exchange. We were using our domain for both incoming and outgoing mail until Earthlink decided to block all port 25 SMTP mail servers. So I had to change the outgoing mail serverinformation to mail.earthlink.net on all of our workstations. At the server I enabled Microsoft Exchange Internet Mail Service. Mail delivery works fine on all of the Windows 98 Clients. However, mail from the Windows ME Client gets stuck in the IMS Delivery Queue. Two days later the system sends back a message undeliverable notice.