First, McGee says that they don't solve any real indexing or crawlability problems--sitemaps just mask them. "If you have a 100-page site, and the spiders can only access 25 of your pages, fix your crawlability problems," he says. "Using a sitemap to solve crawlability issues is never a good idea. It's like putting a band-aid on your chest after open-heart surgery."
And if the engines are crawling your entire site, but only indexing a few pages, then working on things like the content and links on those un-indexed pages is what you should be doing--not worrying about a sitemap, McGee says.