Had a nasty run-in with Outlook 2007 the other day: despite the internet message format being set to HTML, recipients not using Outlook would still receive mail with attachments as RTF with an unreadable winmail.dat file attached to it.

and

Clueless, I started poking around and finally resorted to Google to find out what was going on. Apparently, there is a separate setting per e-mail address in your contacts list, stating what format that recipient should be able to receive. By default, it is set to Let Outlook decide which basically tells to use the default in Outlook options (thus, being HTML).
However, this is also the choice of Always use RTF, which basically forces Outlook to always send out e-mail as RTF (with winmail.dat as attachments) for that particular contact, totally ignoring the internet message format set in the global Outlook options. This is a pretty logic conclusion, but a bit unfortunate if you have a lot of contacts who have this option set.

Fix it

There are a few ways to fix it. The first and most tried method is by simply adjusting the setting per e-mail address and per contact. How to change the setting depends on your version of Outlook.

Outlook 2007

Open the contact's properties, double-click the e-mail addresses and set the internet format to Let Outlook decide.

Outlook 2010

Open the contact's properties, click on the presence icon in front of the e-mail address; the presence indicator pops up. In the options menu, choose Outlook properties and change the internet format.

Note on Sharepoint Contact lists

At the time of writing there is a problem with shared contact lists through Sharepoint not correctly saving this flag to the server. Apparently, Sharepoint's default setting is to use RTF. Changing this flag with Outlook 2007 saves it to the local cache, but a new synchronisation of new contacts resets the flag back to RTF, making the use of Sharepoint lists basically a huge hassle if recipients are not using Outlook.

Local Exchange installations can circumvent the issue by using shared contacts through Public Folders, but for Microsoft Online, this is unfortunately not possible as they do not support Public Folders.
They are currently aware of the problem but cannot help out as it seems to be a design flaw in Sharepoint itself.