When you send mail over the Internet from a Microsoft Exchange Windows client or an Outlook client, a file attachment called Winmail.dat may be added to the message. This attachment contains the Microsoft Exchange rich-text information of the message being sent. The Winmail.dat file may not be useful to non-Microsoft Exchange recipients. The information in the Winmail.dat file may appear on the receiving end as binary information at the end of the mail message.
There are 3 excellent Microsoft Knowledge Base articles you can follow below which explain how you can prevent this from happening:
For Outlook 2003 - 2007 Users: http://support.microsoft.com/kb/278061
For Exchange Servers: http://support.microsoft.com/kb/138053
For Exchange over IMC: http://support.microsoft.com/kb/149203
Once the changes have been made, please test by sending another email to fax and make sure you no longer receive the failed email notification.