Interesting point. I can only do very limited testing, but I just sent an email with one very long line from mutt on my laptop to my gmail address. The long line was not broken, and the display flowed perfectly on the gmail client on Android.

I think you should be able to use a hook in Mutt to process the markdown to HTML (using Pandoc) before sending. I've never tried anything like this—it has interesting possibilities.