Recuerdo que en algún lugar cerca de Panther (cuando aún usaba Mail.app), los usuarios de Outlook (en Windows) tendrían problemas con mis archivos adjuntos. Estaba tratando de encontrar la solución que tenía que aplicar y creo que este enlace tiene más (si No toda la información. Esencialmente era un error de Outlook, pero había una solución. Se explica allí.
En cuanto a lo "en línea", es porque Outlook está leyendo el correo electrónico como texto enriquecido con información UUencoded en línea. Como ya se sugirió, intente comprimir el archivo adjunto o envíe mensajes de texto sin formato a esos destinatarios (hay un atajo para convertir fácilmente un mensaje a texto simple, vea la respuesta de Kyle).