Demonstrated in edits added at T44886#5508222:
Both the delete and the move should have triggered jobs to update sitelinks, but it appears that the move job probably ran and failed first before the delete job then ran.
The actions will continue to be applied separately, a delete and then a move, and this case needs to be covered.
One possible option would be when creating the move job, see if the target was recently deleted, if it was wait for a while and expect that the sitelink should be removed, before the move job proceeds.
I'm not sure if the job queue has a way of seeing if a job with a given spec is queued? if it does that could also be used (but last time i looked this wasn't possible)
Simply adding a delay to all move jobs might also work, but would be less reliable that idea 1.
Moving to product backlog as the technical approach etc seems to be known enough and this is not on the card of the tech prioritization I dont think