You can try A1 Sitemap Generator. Here's a page with xml sitemap tutorials (create, upload, submit, ping)
The best option is to create your own sitemap creator, so you know what it does, you tell the script what to index and what not etc. Plus, you can also add a fuction to auto-update it daily
Well There are Several plugins are available in this regards but i preferred the Google XML Site map Generator and if You are using word press self hosted Blog the best available plug in for self hosted blog is WP XML Site map Generator is the best option..
I have always used xml-sitemaps.com but only on the assumption that there was not much between them. Should I be shopping around?
Sorry, no answer on this one. Perhaps you can make multiple sitemaps and try submitting them to webmasters. That also works as well as having a single sitemap file.