The "Delete from history" menu option removes all visits to that URL from your history, and also removes the shortcut. I don't think Firefox keeps a record of the URLs you delete using that menu option (that could be a privacy problem if you are trying to get rid of the record of your visits to that site), so I don't think there is any place to look for those URLs now.

If you recall how you found the site, or when, perhaps you can use your other history to reconstruct the path and find a link back to the site from wherever you found it before (article, search result, email message, etc.).