1. A non-transitory computer-readable storage medium having executable computer program instructions embodied therein, comprising: instructions for receiving a search query from a user; instructions for saving the search query in a persistent storage medium; instructions for transmitting the search query to a remote network search service; instructions for receiving a first search result set from the network search service based on the search query; instructions for retransmitting the saved search query to the network search service to obtain an updated search result set; instructions for identifying search results of the updated search result set that were not present in the first search result set; instructions for providing at least the identified search results to the user; instructions for determining a count of the search results of the updated search result set that were not present in the first search result set; instructions for computing a search backoff time based at least in part on the count; and instructions for waiting the computed search backoff time before retransmitting the saved search query to the network search service.