Hard to tell what's causing this, could be all kinds of things. What the sitemap does is create a DataObjectSet of every live page on the site. So even one faulty page could maybe cause the problem. If your site is very large, that could also slow things down. First thing I would do is try and upgrade the site (a test version) to the newest stable SS version.
In the case of the Locale issue: this could even be a problem in one of the de_DE.php language files - you can check this by temporary removing/renaming your languagefiles one-by-one, especially the ones in custom modules and check if it now works.
Would be nice if you had access to your servers logs and see if anything else occurs besides timing out...
You could try and comment out parts of the Items() function in GoogleSitemaps/code/GoogleSitemap.php, if you're up to that, and see where it goes wrong, that would maybe give you a hint.