No direct answer when reaching support.

It was some kind of penalization for some general terms like "video chat app". Before the app was in the first 10 or so and after it disappeared completely from results. But searching for the app by full name works. Also it disappeared completely from the "social" category listing.

They tols us that "search algorithm is secret and complex" but we had a previous experience like this one with an app that had unallowed content in Google Play (unreviewed images from users showing erotic content) This one was penalized with some months of disappearing from general terms search results and listing.

But now no explanation. At least they should give you an answer if there is some kind of infraction of content policy.