I used "Translate URLs?" before and since upgrade to above specs it is just working like random. Some get translated (even original urls to other languages), other not. Can't see any pattern as with every link cleanup it affects other URLs.
Joomfish basic router is active (as it can't be deactivated)

Hi,
Is the "Always use language" option in JoomSEF enabled? If it's not, try enabling it.
What versions you used before the upgrade? Have you upgraded only JoomSEF or JoomFish too?

Hi,
I used Joomfish 2.1.0 (with deactivated jrouter) and JoomSEF 3.8.2(or 3?) with subdomains for each lang.
'Always use language' doesn't seem to have any effect on titles, it just adds &lang=xy to it.

Does this problem happen only with URLs to some specific component? Or does it also happen to links to articles?

no, not a specific one. Happening on basic joomla stuff but also on components, for example moset tree.
It seems to be related to the first used language on the link, so if the first access to an url was done with, for example, german, the other languages get the same (german) title/url.
The page (language) content is always correct, it's just the URLs.

There will probably be some incompatibility between JoomSEF and new JoomFish version. We'll test this issue and let you know.