Resetting preferences did not work. cmd + opt + shift at starting bridge led to the same result and same message.
Reinstalling the app in the normal way worked. I did not use the cleaner tool. For a "normal" user this seems a bit too advanced - especially as there are so many warnings issued by Adobe to use this tool in the very correct way. Anyway, I deinstalled, including all the preferences deinstalled. Reinstalled Bridge and now it seems like it workes even better, ie. a tad faster.