It looks like under certain conditions, Auto-playlists do not notice that the data they're operating on has changed and do not know to refresh themselves.
I have an Auto-playlist called "Unrated 4" whose rule is:
Source: Music Library
ALL of
Playlist IS All Unrated
Album Rating IS 4
and "All Unrated" is:
Source: Music Library
ALL of
Rating IS NOT 5
and ANY of
Rating IS 0
Rating HAS NO VALUE
Rating IS [bomb]
Last Played IS NOT IN THE LAST 28 WEEKS
Playlist IS NOT Skips
Playlist IS NOT Videos
If I'm listening to a song from my "Unrated 4" playlist, and then I rate the song 3 stars, and the song finishes playing, I would expect the song to no longer show up in "Unrated 4" (both because it received a rating, and because the Last Played is minutes ago). Sometimes this seems to work, but sometimes the song remains in the playlist.
The workaround I've found is to make some small change to the playlist rule. For example, I edit "Unrated 4" to have "limit to 10 items selected by Random", and then remove that limit again to put the Auto-playlist back into its initial state.