Problem with caching after the last few updates

For some reason I have to clear the Joomla cache every few days.
If people tick the 'remember me', it works most of the time, but sometimes it doesn't really register that people are logged in, so that the wrong menu'es are shown (for not logged in people).

CB doesn't have file caching so I've no idea. Any caching we use is at run time for variable caching (basically just static variables). Do not use Joomla page caching or you're going to have out of date data like that as the way page caching works is it captures the buffer, stores it to a file, and serves that file for the next XYZ minutes. If you've a dynamic environment this does not work since that buffer is basically out of date the minute it's cached. The caching would need to at the very least be per session, which as far as I'm aware it's not.

Your Joomla cache certainly should not have a lifetime of days, but rather minutes up to an hour purely to prevent duplicate subsequent requests and reduce server load. Only pages acceptable to have days worth of caching are like Joomla content.

It is set to 5 minuttes, but nevertheless after the later updates to CB antispam the 'keep me logged in' is a mess if it's set.
I've disabled cache for now.

I don't know how CB AntiSpam could have any affect on that as its login behavior is attempts and captcha checks. If you're using neither it does nothing during login. If you're using either try disabling those behaviors and see if issue persists.