Well, the best resource to ask would be Google. If you haven't already done so, log into Google.com/webmasters and they'll give you enough to read to last a month of Sundays....
As for my take on it, it probably depends on the site, to some extent. A site with a few pages, and a good navigation/link structure, will likely not need to provide all the URLs to Google.
Large sites/product sites, with constructed URLs (e.g. content varies depending on variables sent via GET, or POSTed in a form, etc.) might gain more advantage from it. On OMBE we do submit a sitemap (actually about 6 of them, IIRC), generated every 48 hours. They contain URLs for every product (about 150K these days), every category page, filter page, etc., every store in the mall, (we add products most weekdays, but stores & categories not nearly so often), all the other pages (which hardly ever change).
As for how much it helps ... again, it depends. I was able to get us a little higher on Google and increase our inbound SEO percentage, but it hasn't really been enough to impact the company's bottom line significantly (it might be argued that it has kept us afloat, I guess). I am often a bit miffed when I look at things like PageRank and see that some of our competitors have significantly higher PR than ours, and that, despite the fact I'm submitting 300K+ URLs, Google's index only contains less than 25% of them....
