Hi, I'm having a similar issue. My main apps, iKana touch and iKanji touch have both been on the app store for nearly a decade and generally enjoyed good rankings. Both apps see fairly frequent updates, have 4-5 star ratings and hundreds of positive reviews. The rankings of both these apps have fallen immensely – from being in the top 10 to being 40th-60th on my main keywords. As you can imagine next to no one finds them anymore.
I tried converting iKana touch from paid to free with IAP and initially saw some great download numbers (I must have been featured somewhere for a couple of days), but I'm totally lost in the rankings for all my main keywords. After playing with my keywords, app title and subtitle I do now at least rank in the top 10 for a partial search on my app's full name ("iKana - hiragana and katakana") which is great, although it makes a mockery of the idea we're not supposed to be keyword loading our titles. But still with any other variation on this and I'm burried. It's infurating to see apps which have not been updated in *years* with *zero* ratings 10s of places above mine in the search. This nonsense is on the verge of putting me out of business because sales have become so poor as discoverability is basically zero.
If anyone has any help or advice I'd be deeply appreciative, but I guess given it's over half a year since this topic came up we're on our own here