This situation is frustrating for me because I'm probably missing out on some very helpful applications. This situation must surly be frustrating for application developers because timing of it's release it extremely important. It's probably also frustrating for Apple because they realize there is the gap created by the exponential growth of the App Store.
The solution, I believe, can be partly solved with a better search engine on iTunes. First, in addition to keyword-based results, Apple should let the number of downloads and ratings influence the results. Second, Apple should include paid search results with regular search results. They should structure it exactly like regular search engines where developers bid on keywords and Apple displays relevant applications. Developers are then charged when either the application is viewed or downloaded.
These changes will help with a couple of items. First, this will help users like me find better applications easier. Second, it gives newer developers a chance to be seen. Third, it provides another stream of income for Apple. It's a solution which is simple and fair.