I use both the free online generator and PHP script regularly (and have done so for quite a while) and am generally happy with both, except that 500 pages with the free generator often don't cut it, and it becomes a major pain to install, configure and upgrade the paid script if you run more than a few sites. In addition you have to keep a constant eye out for memory, bandwidth and disk size issues.
So I, for one, would be willing to pay a reasonable monthly subscription for an online service such as the free generator, just with all the features of the script version and a scheduling function. That way I won't have to worry about any of the possible memory, bandwidth and disk size issues mentioned, nor upgrading, and can simply concentrate on scheduling sitemap generation.
I understand that there would technical challenges such as being able to update the sitemap files on a remote computer, and you may need to implement size/frequency limitations to deter abuse. (Maybe a subscription sliding scale according to the number of pages, etc.?) But I still feel such a service has its appeal.
Alternatively, institute a subscription or pay-per-use for the free online generator that allows more pages to be generated and downloaded.
Just my 2 cents!