Why catalog job is run on the storage/media ?
It helps to read the content of the media and generates the FH and XML catalog files. When the BE services start, these catalog files are read and only metadata is added to Backup Exec Database (actual files remain in BE Install Path\catalogs folder). When BE console is loaded, it reads the catalog metadata entries from BEDB and shows what backup set are available for restore.
If the catalog files are present, then you will see the backup set and you can make the restore selection. If the backup set is not visible, the selections cannot be made as the info (catalog files) about the backup set is not present in BE Install Path\Catalogs and in this case you will need to catalog the media/storage and then when the set is available, you can create the restore job with the backup set selected which you want to restore.
To conclude if the sets are not visible, you cannot make the restore selection as the sets do not exist and hence you will need to run a catalog job. More info in below technote.
Backup Exec Catalogs