None of the clients using Exchange e-mail can successfully send an e-mail message to an America Online recipient. We do not get an undeliverable message from the Exchange Server. It appears to just drop off the edge of the world.
Are we sending it in an improper format?
Go to the Exchange Administrator program and check your Internet Mail Service Connector. Check the Queues and see whether messages are piling up in the outbound queue (I'll bet they are). Double-click one of the stacked-up messages and you should see some sort of explanation for why the message didn't go.
From there you may have more success troubleshooting it.