Maybe a perfect solution isn't easier, but it should be very easy to improve the mess that is the app store. Let's start with a very simple suggestion:
Searching for an app by name should return that app.
Yeah. It's much better than it used to be (today when I search for Tweetbot it pull up Tweetbot) but that hasn't always been the case. You still have the issue that they clearly have a CDN with a slow refresh so that when an app is first released you can find it via links online or features on the front of the app store but not by searching the name.
It seems like an unjust reward for already successful apps - they're given the right to steal search results for a competitor's app name.
That's a good way to be sure you can be found. If you type "Vima"[1] in the app store, I guarantee you find my apps :-)
[1] Vima is greek for "pace", which is how we came up with it. Full title is "Vima - GPS Run Tracker"
Sure it is. Stop trying to funnel the entire marketplace through a single vendor-controlled retailer.
I actually think the store is in a pretty decent state right now overall. You can't possibly make everything very visible. It's a pretty good deal to be on the shelves, now you just have to work harder on your own promotion.