The Recently Deleted folder only holds programs that can be restored. If your shows were deleted because of lack of space then those programs were overwritten and as such would not appear in Recently Deleted.
As for the recoding history... It lists shows by date recorded, so that's not going to be much help either.
If you use the Search in the HDUI it has a way to list entire seasons of shows, even if they're not in the guide, and allows you to record ones that are in the guide or setup Wish Lists for ones that aren't.
Developer for VideoReDo