This code will get you data set of all pages that are stored in Recycle bin. In your case it might make sense to cache e.g. the List of DocumentIDs of pages in a recycle bin for a quick access to data and to avoid executing unnecessary queries each time a user goes to old page.
private DataSet GetRecycleBinPages()
{
int topN = -1; // all pages
return VersionHistoryInfoProvider.GetRecycleBin(SiteContext.CurrentSiteID, 0, null, null, topN, null, DateTimeHelper.ZERO_TIME, DateTimeHelper.ZERO_TIME);
}