As part of the work done for improving acessibility in Moodle, XHTML validation has been broken.

The 'span' element does not support the 'tabindex' attribute (see http://www.w3.org/TR/html4/struct/global.html#edef-SPAN), but this is being used in the navigation menu which is present on almost all pages. Consequently almost all of Moodle fails validation (regardless of theme chosen).

This problem occurres in:
/blocks/navigation/renderer.php
/lib/outputrenderers.php