Do we have any details / differences between the users that work and that don't work? Do you have any log indicating any (database) errors? Do you use only the joomla core auth plugins or is some extension involved too? Why do you know that the last visit time is incorrect?

Actually I need to close this, because the affected users don't have this problem anymore. Maybe it was a problem caused by cache or whatever. Everything's fine and everything's working properly!

Thanks for this very quick response, you're doing a great job!