I suspect that Exchange 2010 is configured to use the TNEF message format when sending to certain recipient domains. Where can I check (server-side) to confirm if this is the case? I'm familiar with the Outlook settings for TNEF and that doesn't appear to be using TNEF there.
One way you can check is to see if you have any remote domains configured under your Organization configuration =>Hub transport in the Exchange Management console. In there should typically be the default setting for all domains but if you have any additional domains set here they will override the default settings and use those for traffic destin for those domains.
I would start from the options described in this Microsoft article.