Let me say it again: search is truncated and random. But not random per search. More like per day or whatever. I assume the servers build a nightly search index, so it does not take a minute for each search.
You will show up on one day and not on the other. It is supposed to cycle the relevant items. Your dog or was it cats even was on place one of search. But itch will not tell how it works, because people will try to game the system.
I remember a thread where the dev complained that the game was not showing up in search despite searching for the exact title.