That internal versus external split plus winmail.dat sightings is the fingerprint of one specific cause: your messages leave in Outlook's Rich Text format, which wraps everything including attachments inside a Microsoft only container called TNEF. Exchange recipients unwrap it invisibly, everyone else receives the container itself as winmail.dat or a mangled attachment.
1
Set your default away from Rich Text: File, Options, Mail, and under Compose messages set the format to HTML.
2
Fix the internet handoff: same Options page, scroll to Message format and set When sending messages in Rich Text format to Internet recipients to Convert to HTML format.
3
Hunt the per contact override, the sneakiest cause: open the affected recipient in your Contacts, double click their email address to open properties, and if Internet format says Send using Outlook Rich Text Format, change it to Let Outlook decide. This per contact setting silently outranks your defaults and typically arrived by replying to something ancient.
4
Send the affected recipient a fresh test after the changes, replies to old Rich Text threads can keep inheriting the old format, so start a new message rather than replying to confirm the fix.
If a recipient reports corruption without any winmail.dat and the TNEF settings check out clean, the second suspect is antivirus mail scanning modifying attachments in transit on your side, testable by sending one message with the AV's Outlook integration paused. But the split you describe, internal fine and external broken, points squarely at TNEF and the settings above end it in the great majority of cases.