http://validator.w3.org/

Does it help to have your website completely valid???

AFAIK, no.

Having clean semantic markup will help though. The less tags cluttering up your code, the better the spiders can scrape the content. Also, using headers as they were designed. Search engines weigh words in h1,h2,etc. tags more than other content.