When a search is performed, I am getting results that are from deleted messages.
This FAQ is only for versions prior to 4.1, and some early 4.1 releases. Other versions have entirely new search engines and automatically update to reflect deletions.
It's time to rebuild your search index. The search index is designed for efficient searches. As items are added to your site, the index is added to. However it is not possible to delete items from the search index. So every so often it's a good idea to rebuild the search index.
As sysop, enter the Control Panel, and click the "Create Search Index" down towards the bottom of the page.