I've tried out Google's sitemap utility quite a bit, and found it somewhat useful. Nothing compared to their analytic software, but helpful nonetheless. Effective? Not sure yet, the jury on that has yet to reach a verdict.
Now I'm making my way through Yahoo's Site Explorer. I've only gotten as far as registering a domain, but it hasn't been verified. Unfortunately they only have one method of verification, which is to upload an html file to your server's document root. This is all fine and dandy if you don't use mod_rewrite, but I do, so all uri's that end in .html are actually rewritten to index.php?something=somethingelse&and=so&on=true. I'm trying it anyway but it probably won't work.