Some other considerations that aren't really part of the primary goal and so might not be part of the accepted solution, but might help direct effort in more successful directions.

I would like the rules for how we detect that a post "isn't formatted" and for how we transform it into a formated post to be very simple to communicate. People being surprised by a post being declared "unformatted" or not should be rare. People being surprised by how formatting got added should be rare. I'm fine with people more often being disappointed with how well the formatting was intuited, especially if they are disappointed but immediately understand why the very simple rules involved lead to those results.

This is meant as a fall-back for formatting nodes, not a replacement.

I find some key concept in POD to be ubiquitous in "simple formatting" schemes and so I think these would be very useful both for very often getting at "what the posting monk meant" and making the rules easy to understand.

These are: 1) Formatting is only done to paragraphs. 2) Paragraphs are separated by blank lines. 3) A line of only whitespace characters is "blank". 4) "code" has indented lines. Then you enclose each paragraph in either P tags or C tags, depending on whether it is "code" or not.

Yes, please join adjacent code "paragraphs" together so that they end up with only one set of C tags around the whole run and with the original interparagraph spacing preserved.

I wouldn't add "the little stuff" nor would I consider the presense of "little stuff" to be an indication of "the node is formatted". "Little stuff" is tags like A, B, I, EM, STRONG, maybe BR. A single <p> or <code> or <c> should probably count as "already formatted".