I would start with upgrading to 4.7, because it's generates more compliant code.
There are inline HTML aligns which are not valid and I even see some <font> tags (yek...;-).
Change them to CSS to make the page validate, but they will not have any influence on the SE.
Structiutally incorrect HTML does, check that.
But if your first concern is SEO then I would use another menu component.
Best would be a CSS based Unordered list menu like Housmenu or CSS nav menu
The new default menu is also better then Solpart, but not as good as an Unordered list menu for SE.
In my tests I was able to create an XHTML transitional valid page without any core changes using 4.7.
At the moment the visibility skinobject doesn't validate and some of the modules don't, but the core should.