The rebuilding of our search indices does not work as intended, and we have no clue why yet. This then affects "new" geocaches, where new in this case actually can be a while.
Updated the search indices manually now. Still a bit confused of why it doesn't work automatically though.
UPDATE: We have found and solved an issue. This should work from now on, though we haven't tested it yet (have to wait for new geocaches). The search indices are updated once per hour.