The deletion option within the help desk is a soft delete, in this scenario this means you cannot locate the company you have deleted without going into the back-end database.
If you do this then you should find a company table (or something similar), locate the corresponding company name and find the ID referenced in the table. With this ID you can then query the tickets table and find all the tickets by that ID.
They may have changed this in the latest versions whereby you can skip getting the ID and just locate the company name, however I doubt this has happened.
Thanks and that is the unfortunate answer I was expecting. I like that it's a soft delete but then I don't see any reason why they wouldn't allow you to select a check box in the advanced searches that would allow you to see and search based on things that have been deleted. I can certainly see use cases where you would want to search for tickets based on a company that has been removed.