I wouldn't worry about the sitemap location too much. I doubt it's going to affect the final results that much. 100,000s magento sites don't have their sitemap in the root folder.
If you're worried about it though, and you can't get the hosting company to get the permissions right, I'd continue generating the sitemap in a subfolder and then create a symlink at the root level to the subfolder. This means that Magenot still only needs permissions to write in the subfolder but you can link to it from the root level.
----
If you've found one of my answers useful, please give "Kudos" or "Accept as Solution" as appropriate. Thanks!