1. A computing system comprising: a network interface; at least one processor; a data storage; and a program logic stored in the data storage and executable by the at least one processor to: remove a given media item from a queue of media items; add to the queue an indication that the given media item has been removed from the queue; after adding to the queue the indication, receive, via the network interface, one or more requests for one or more media items from the queue of media items, wherein at least one of the requests for one or more media items includes the given media item; after receiving the one or more requests, determine 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; and after determining that the computing system has received more than the threshold number of requests, remove the indication from the queue.