1) Import all images (only those not in the Catalog will select) (ie. the photos you 'Removed' from the Catalog)
2) Open the [Previous Import] list in the Catalog Panel
3) Select all and Delete from Disk.
The degree of difficulty may depend on your folder structure, and if you have always been importing ALL your photos in the past. (ie. there may be photos not yet imported that you do NOT want to delete!)