Some people say that your website just has to be W3C compliant in order to be considered fit for the search engines. Others say that search engines like Google favor HTML over other forms of coding. What is the truth about this?
W3C compliancy is a good idea, but it does not help search engine rankings. It just ensures that both people and search engine are able to access all of your website. I don't think Google favors html over any other kind of code. They do favor pages with a higher text to code ratio. For example, you would be better off using css div's instead of tables.
I agree with vansterdam, I have some websites that are compliant, and others that I know aren't. All are doing exceptional. Backlinks > compliance
I would say that w3c validation is good because it will help browsers render your site faster and accurately and the same would be true for googlebot, you are assured that googlebot will give correct weights to keyword in your page. But again, it's 'good to have' and not mandatory
Having valid code would probably be a good thing to do, and Google recommends it in their Design & Content guidelines.