1. A computer-implemented method comprising: determining, by a data processing apparatus, that a given user device previously submitted a search query; determining, by the data processing apparatus, that the given user device requested presentation of two or more pages of search results responsive to the previously submitted search query; determining, by the data processing apparatus, that no user interaction occurred with the search results presented on the two or more pages of search results presented on the given user device responsive to the previously submitted search query; in response to determining that both the two or more pages of search results were requested and that no user interaction occurred with the search results presented on the two or more pages of search results presented on the given user device, determining that a user dissatisfaction condition has occurred; in response to determining the user dissatisfaction condition has occurred, determining to perform a remedial search operation that includes identifying, by the data processing apparatus and as a remedial search query for the remedial search operation, a related query for the previously submitted search query that is different from the previously submitted search query; receiving, by the data processing apparatus, a current search query from the given user device, the current search query being received subsequent to the previously submitted search query; determining, by the data processing apparatus, that a topic of the current search query has been classified as being similar to a topic of the previously submitted search query; and in response to determining that the topic of the current search query has been classified as being similar to a topic of the previously submitted search query and in response to determining to perform the remedial search operation, performing the remedial search operation by providing, to the given user device by the data processing apparatus and for presentation on a search results page that includes search results for the current search query, a link that, when selected, initiates a search using the identified remedial search query.