Zend certified PHP/Magento developer

Deleted Products Still Showing in Search Bar

We recently had to let our webdeveloper go and dont have a new hire yet. We are experiencing an issue with deleted products continuing to show up in our search bar. We’ve cleared caches and ensured the products are removed. No one here is knowledgeable enough to know what to do about this but its causing customer headaches so we need to resolve this. Can anyone give us a step by step on where to go and what to do to try to resolve this?