"No emoji found" in Google Japanese Input
I found the answer 10 minutes after posting the question, that's silly.

The trick is, you must search in hiragana. Even if your locale is English (like in my case).

For instance, search for ねこ instead of cat or 猫:



Most users type the hiragana before getting the kanji anyway, so it kind of makes sense if you think about it afterwards.