Sorry i dont have a solution but i have the exact problem!
I called microsoft and they have told me that if the attachments are showing in the sent box then is is most likly a problem with the customers computer... seems very starange that all of a sudden half of our customers are having issues receiving their invoices ( Send through our accounting program as a PDF attchent. please let me know if you find a solution
If the attachment is not recieved by the recipient and the attachment is visible in sent items, this is what needs to be done. You need to configure your Outlook to use Plain Text. Switch if you are using Rich text or HTML format. This should resolve the issue.