Transaction type of “case” is not available

Saved Search > "Deleted Record" as the record type. Then on the search criteria define your Record Type as "Case". I think it should be there (I don't use cases here). Bear in mind that all the actual data is deleted. You'll just get to see the basic identifying information for the records deleted. And there might be a limit to how far back you can go for certain record types IIRC.