ummm, if all the pages are indexed by Google, you don't have to make a sitemap, but to be sure, have a sitemap and submit it to Google
I think site map is necessary for your site. If you have many navigation on your website, you need sitemap. For xml sitemap you can try here!
I believe sitemap is the faster way to help search engine spider to understand the structurs of your site.
How do you know for sure that your site is well indexed? Say a vBulletin forum that has 155,000 posts and 12,000 threads. How would I know if that is indexed well?
Hmm... maybe I'll look into them I guess. I've heard from others that if your site is relatively old Google knows about it, and it's pointless to make a sitemap.