I think I may have found what is at the root of this problem but I don't know if it is going to help.
After sending messages to myself before and after a corrupt paste command, and then viewing the raw source of those messages, I found that the html formatted version of the message is ballooning with verbose tags.
My basic 14 line signature resulted in 140 lines of html code (I copied it into Dreamweaver to get a better look).
Pasting one word in the middle of a line (which then appeared 2 lines above) increased this to 214 lines of code. The resulting code was a complete mess of nested and jumbled up tags.
I noticed reference within the opening tags to webkit which I had heard of but know litttle about but I did some research and came up with this page : http://www.webkit.org/blog/1737/apple-style-span-is-gone/
If that link gets messed up, just Google apple-style-span-is-gone
As far as I can make out webkit is used by Safari and Mail to display and work with html content. It was originally created by Apple but is open source. The above article is one programmers contribution to the open source project to fix what I suspect is the root cause of all these problems including people's comments about styled messages taking a long time to send. Note the authors comment ...
<the problem> was particularly apparent on mail clients that used WebKit as the editor such as Apple’s Mail ... In some case, an e-email consisting of 3 lines of text consumed 3MB in HTML because of nested spans created by WebKit and other mail clients.
Unfortunately it's not as simple as downloading a newer version of webkit. The webkit.org wiki faq states that ...
Replacing the WebKit.framework that ships with Mac OS X or any of its components with those from a locally built copy or a nightly build of WebKit is HIGHLY discouraged. Doing so will likely leave your system unusuable and cause a tear in the fabric of spacetime—so don't do it!
I don't know for sure that this is the root problem but it does sem to fit and explains why the symptom has been seen across 10.4 - 10.7 and different versions of Mail. I suspect the problem started for each person with the download of a particular Safari version which included a problematic build of webkit.
Anyway, thats about as far as I can take it so I hope someone else is able to pick up the thread and get closer to finding a solution. I suspect, however, that in spite of this knowlege, we may still have to wait for Apple to build a fixed version of webkit into a new Safari version.