I think this <code></code> and <p></p> parser would be harder to implement than it seems (even keeping in mind your counter points). [...] There is also the question of how do you parse out incorrect code/pseudo code.
Does that parser have to be complete and perfect? All we want at this point is a simple check that the raw posting text contains one or more <p> and zero or more <code> or <c> tags. (Tags, not elements. We don't even have to check for the closing tags. Existing code handles missing or mis-placed tags quite well.) Unless that condition is met, the poster will see a hint that (s)he should check is posting. Implementing those checks could be done using one or two simple regexps.
Today I will gladly share my knowledge and experience, for there are no sweeter words than "I told you so". ;-)