Deleted objects no longer appear in the folder where they were deleted from. There are several ways you can view deleted objects that have not been permanently destroyed.
The dialog indicates the Restore Location hierarchy where the object would be restored to, which is normally the folder from which it was deleted. However, if that folder (or a higher-level folder) has been deleted, the location will change. If the folder was renamed (or a higher-level folder was renamed), the Restore Location will reflect the renamed location. You cannot modify the properties of a deleted object (the OK button is disabled).
Add a Deleted column to the view to make it easy to sort the list to co-locate all deleted items.
Since the list of deleted items in a cabinet can become quite large, if you know the folder in which the items of interest resided, you will have an easier time locating them if you issue the command on the folder rather than the cabinet. Note that deletion-relevant columns are included in the view.