SEOMike - 11:00 pm on Feb 8, 2011 (gmt 0)
Depending on the site, I think I'd go for valid HTML. I have a client whose HTML was so bad that Google only found 19 of the 50k+ pages. After fixing the HTML the number of pages indexed went through the roof. The number of links soared too because Google could index the pages with links pointing to them and award proper credit. Link count went from 9 to 15,000 in two weeks and there are over 1.6 million links credited now. The site had been up for over a year when I started for them and hadn't accomplished anything.