Not all users wanted a refreshed list each time, which wasn't an option in MMW4. So in MediaMonkey 5 you can now choose either method.

I just needed to find the auto-refresh option via Google...

No. It wasn't set.

But why this incompatiblity to MM4? What is your recommendation to an overarching update of an huge autoplaylist collection to the desired behaviour?

Are you sorting on an option with Auto-Refresh? That would be needed for this.

Addition: It seems to be a difference whether a) I create a AutoPlayList which selects only by tag attributes (e.g. genre = Pop + rating = 3 stars) or whether b) the AutoPlayList is a combination of several sub-AutoPlayLists. Error appears only in case a).

Once a random AutoPlayList is configured, it choices a random sequence correctly.
But with any next request of this playlist it keeps the firstly chosen sequence and doesn't rearrange anymore.

How can I get back the old behaviour of MM4?

MM 2024.0.0.3018