OK, I've now tried it with global caching on and local module level caching on for the menus.
I cannot reproduce the bug at all now.
It seems with the System Mootools Upgrade, the links in the hierarchical menu system work fine now even with intensive language switching.
I'm quite happy with GTranslate now.
I am very curious whether I will see increased, valuable traffic to my website in the next few months.