Fix #2116 by generating a custom skip token for search queries

Fixes #2116