Sounds a bit buggy - can you set up a new service and see if it happens there? Also where are you publishing?
I was able to replicate the problem with a brand new Pub Srv. This one was just to my Hard Drive (rather than a web site) and indeed it too exhibited the same issue.
I took around 50 images, put them in the Pub Srv and published. Then I added a red color label to about half of them which moved them to the “republish” section. I then selected them all those in the republish section and used the “Mark as up to date” tool. All but around 5 moved to the “Published” section. But then over the next 3 or 4 seconds another 4 or 5 which had moved jumped back from the Published section to the “modified” section as I watched (while not doing anything).
It’s like something going on in the background was marking them as re-changed. I wonder if this could be related to some of them belonging to synced collections and the synch to the cloud background process is somehow marking them as modified? To test this, I repeated the process but before setting them as “up to date” I waited for the sync process to finish, then paused syncing and then marked them to “up to date” but yet again not all of them moved to the published section. So, perhaps, cloud syncing may not be involved.
I should note that the number not moved is random as is the specific images
Is anyone else able to replicate this problem?