Hmm enabling SEF seem to make it even worse.
The pages then generates a 404 on all links:
Not Found The requested URL was not found on this server. Additionally, a 404 Not Found error was encountered while trying to use an ErrorDocument to handle the request.
I had to take it off again and disable SEF.
This makes it even more complicated then because the links are still failing and I have no idea why it does that in the never version of TikiWiki.