Ricordo da qualche parte intorno a Panther (quando usavo ancora Mail.app), che gli utenti di Outlook (su Windows) avrebbero avuto problemi con i miei allegati. Stavo cercando di trovare la soluzione che dovevo applicare e credo che questo link abbia la maggior parte (se non tutto) le informazioni. Essenzialmente era un bug di Outlook, ma c'era una soluzione. È spiegato lì.
Riguardo la cosa "in linea", è perché Outlook sta leggendo l'e-mail come un RichText con informazioni UUencoded in linea. Come già suggerito, prova a zippare l'allegato o inviare messaggi di testo normale a quei destinatari (c'è una scorciatoia per convertire facilmente un messaggio in PlainText, vedi la risposta di Kyle).