Tools->Options->"Mail Format" Tab:
Your Mail format should probably be HTML or Plain text. Not Rich Text.
Or if you "Must use Rich Text... Click the "Internet Format" button and make sure it's set to "Convert to HTML format" When sending to internet recipients.
Note: that's where I find the settings on Outlook 2007... your mileage may vary.