I don't mean to hijack the thread but I want to add some information for what I believe is essentially the same problem I'm experiencing.
I, too, published a new plugin for a client recently: zhiing Send-to-Phone. However, if you search for "zhiing" and you have the "relevant" or "highest rated" options selected, the plugin does not appear on the search results. I had similar results when trying to search for galerio's plugin.
Since "relevant" is the default (not even shown when using the sidebar search form as opposed to the search form on the main plugins page) people are not finding the plugin.
Does anyone care to provide some insight into how the search function is supposed to work, and how we can effectively deploy plugins so they are included in the results properly?
Apologies to galerio for jumping in, thanks to anyone who can help us out.