As an Android user, it really is depressing to see screenshots of how clean the Android Market used to be. Nowadays even when I search an app name verbatim it's a crapshoot if I'll actually find it

Best to find a link to a companies app from their website - searching in the store is asking for trouble. Too many hijacked search results.