sometimes we see newly generated URLs that include the whole domain and the wrong (default) language so in frontend the generated link is:
wj15.domain.dehttp://wj15.domain.de/category/requirements

SEF: wj15.domain.de/category/requirements
Real. index.php?option=com_content&catid=55&id=400&lang=de&view=article&Itemid=183

after deleting this one it gets correctly regenerated:
wj15.domain.de/Kategorie/systemanforderungen

SEF: Kategorie/systemanforderungen
Real: index.php?option=com_content&catid=55&id=400&lang=de&view=article&Itemid=183

can't a find a pattern when this happens, seems to be fully random

Hi,

Try enabling the URL Source Tracing option in JoomSEF's Configuration on the Advanced tab. That way when new URL is generated its source will be stored with it, so maybe you can find some pattern using it.
Let me know what you find out or post some examples of the Trace information for wrong URLs.

ok, will try to record some.
While they seem to be random, they never have been seen on default language (en) and never when URLs are updated in backend (&task=updateurls).

just happend after a translation was edited in falang. Before it was working correctly. Sadly isn't reproducable, next edit still keeps the working url.

some more

So the posted Trace Information are for correct URLs? I'm sorry but I'll need them for wrong URLs so I can try to backtrack the problem.
Please let me know if some wrong URL appears again.

no, these posted traces are only from wrong urls.