Outlook attachments won’t go through

I have a user who has trouble sending emails with attachments to a particular client. The following error message is displayed in the recipients inbox:

Type: application/ms-tnef
Part 1.2 Encoding: base64
Download Status: Not downloaded with message

The user sent the same emails to me and I forwarded them successfully to the recipient . I checked the users Outlook settings and MIME is set to base64. What is odd is the fact that the user can send the attachments successfully to several other email accounts but not to a particular one.

Any ideas on what would cause this?