As this screencast video shows ( http://screencast.com/t/gfbso0C1jJ ), if I type in 'mail' in the search box, it brings up the applicable plugins. Then I click on 'Mass Email Sender' and it shows no results. The plugin is for MultiSite only, and my site isn't MultiSite, so I'm guessing that's why it is showing in the search box but not the search results.
Assuming that's the reason it's not showing up, I suggest you DO display the search result but with a big strikethrough or something, and with the "Install" button disabled.
It would make it a better user experience.