Hi Will,
Ouch! That is a lot of money for what should be a straightforward task.
I think you may have missed what I said earlier in that the Unlimited version of XML-Sitemaps is ONLY available as a server install. You do not get a piece of software that enables you to generate the sitemaps externally and upload them.
There are other services around that enable you to generate externally via a web interface and upload. The paid version of freesitemapgenerator.com is one of these, but does require a verification file to be uploaded to the server before it can run. It is a simple text file that verifies ownership of the site.
In the end, if you are not happy with the service you are getting, you have the option to find another web development company who are a better fit for you. If you decided to do that, then the new company should be able to negotiate the change with the old company to minimize disruption.
It makes me a little sad to hear of clients who feel the way you do and I'm sorry that you have had a bad experience with our industry. Thankfully, there are plenty of good companies out there if you should decide that the situation is untenable for your business. For most of us, making things right for a customer who has not had the best of it is a priority.
I hope you can work it out without too much more stress
Sha