Hi Kristin
Yes, I have encountered the issue among a few of my clients. I may be wrong, but I suspect that the recipient is not using a compatible version of Outlook. Try sending the offending emails to yourself and see what happens.
The ultimate solution is to not use MAPI, but rather Direct. Using Direct also avoids the annoying warning messages from Outlook that accompany each and every email. The only downside I can think of is that the emails do not show up in your Outlook Sent folder, but they are in the Adagio email queue.
Steve