Hi.
If you check the 'Windows friendly attachments' checkbox, you have basically done all you can. In my experience, sometimes the combination of Mac Mail and Windows recipients just does not work. Could be Bill Gates getting his own back...
Perhaps every now and then you forget to check the friendly attachments checkbox. You can turn it on permanently by going to the Edit menu, Attachments, Always send windows friendly attachments...
If all else fails, you could try Mozilla Thunderbird
Thunderbird - Reclaim your inbox as an alternative mail client on the Mac.
Mike.