I think I figured it out... Kobo tried to implement a neat "Suggested Searches" feature, similar to the one Google uses to catch typos. (For example, if you search Google for Haloween, it will instead display results for Halloween, then include a link to search for 'haloween' in case that's what you really wanted.
However, for some reason, Kobo extended the replacement table from comon typos to broad association, which can have ... interesting results if you search for books whose title or authors have keywords in the replacement table.
Kobo Search does work the same way though. If you search for Halloween, you will see below the "Displaying results for:" line a "You searched for "Halloween". Click on that small text Halloween and the search results will be for Halloween.
Kobo really should get a grip on this 'feature' fast. Substituting Title or Author Name searches with something completely different is going to attracks lawyers like sharks to blooded water.