One thing search engines thrive on is mark-up that is "well formed". Some people feel that this means mark-up that validates according to the W3C. Well, being valid is one sure way to guarantee that your mark-up is well-formed, but being well-formed can be a bit less rigorous than being valid (especially in HTML 4.01).
Search engines really don't care if your documents use some deprecated attribute, or even something that's proprietary, as long as the code itself is well formed and they can parse it without having to go into an error recovery routine that may or may not succeed. When error recovery fails, then a chunk of the content may well be skipped (been there, done that!)
So closing tags is extremely important - and doing this in the order they were opened is very helpful too. Spelling errors in tags are an awful mistake: <spam> or </spam> is an error I've made more than once, and it orphans the partner tag! It's a good practice, even in writing html, to use closing tags even where they are optional (li, p, td and so on)
Copy/paste errors that accidentally take out an angle bracket are much to easy too create, and this is exactly the kind of error I've made that caused search engines to miss a chunk of a page because the code isn't well formed.
As encyclo said, any valid tag that accurately conveys the semantic values of the document is a good practice. This means that marking up menu links with <li> is a great idea. Divs, even nested divs, convey the manner in which parts of a document relate to each other semantically -- whereas table cells often have a way of splitting related content into relatively dissociated parts of the html.
Lots more to say on this - but I hope I've given some sense of what I'm talking about.