To be honest, there are mixed opinions on the value of validation amongst the theme review team. Although I will freely admit to being something of a standards-purist myself, I have to agree that there is a huge difference between a theme that doesn't validate because of mis-nested markup and a theme with the odd unescaped ampersand. So it may not be as binary as it first appears.
Secondly, no theme can control what its users do with it. All it takes is someone pasting content in from MS Word or throwing a few bits of markup that they once saw "somewhere" into the content and a site with a perfectly valid theme can collapse into a mess of a hundred errors - all because of an unclosed
</p> tag. So of what value was that original "valid HTML" tag?
Then there's the HTML5 themes. The HTML5 spec is still in draft format and the W3C HTML5 validator is still experimental. In fact, it has a distinct tendency to throw up some very arguable "errors" at times.
So, all in all, it's not a implementation issue so much as a "here's a can of worms we really do not want to open" thing.