An example implementation may involve removing, by a computing device, a given media item from a queue of media items. The example implementation may further involve adding to the queue an indication that the given media item has been removed from the queue. After adding to the queue the indication, the implementation may also involve receiving, via a network interface, one or more requests for one or more media items from the queue of media items. After receiving the one or more requests, the implementation may involve determining that the computing system has received more than a threshold number of requests for one or more media items since adding to the queue the indication. After determining that the computing system has received more than the threshold number of requests, the implementation may involve removing the indication from the queue.