We made massive changes to make our site tableless and our code validates now.. Has for months. Didn't see the search engines even notice.
Having validated code is one of the large number of point that search engines love.. it dosent mean that having only a validated HTML for your site can move you to the top in search results..
I'm not sure how much effect it has on the search engines if any, but what valid code will help with is making sure the site can be displayed in different and inparticular new browseres. There will still be older browsers that don't render properly without hacks and slight differences with current browsers but these will be minimal compared to sites with not valid code.
The search engines does care if its vaild or not - but your vistior does. If you can make a vaild site then it will proberly be the same in evey browser.