Just a guess: As far as I remember, network line endings should generally be CR+LF. (See, for example, RFC5322.) When using "\n" on Unix, this generates just the LF, not CR+LF (unless MIME::Lite replaces "\n" with CR+LF). So Outlook may actually behave correct according to the letters of the RFC in refusing to accept anything but CR+LF as a line break. Yes, it's stupid, and I would expect nothing else from Outlook.
Try replacing "\n" with "\r\n" in the message body.
Today I will gladly share my knowledge and experience, for there are no sweeter words than "I told you so". ;-)