Oh man...the solution:

Yes, Everything was world readable. Everything. Even the directories. But they were not world executable, so the cd to them failed for nobody... And I tried it of course as user, who was owner of these...