I see two ways this could be resolved in the code:

1. Load all the tours into memory and translate them into the currently active language - could possibly streamline by only looking in tours with 'translated' values
2. Search through all the relevant language files for matching text - could be very complicated once we have tours from multiple vendors with more complex langugage file naming conventions.

Approach 1 could be performed a 'page'/'display limit' at a time - until you have enough results that match.

Either way the search is done by PHP and not he database.

The only other thought I have is to store the translations of the tour fields in the database

The same goes with Workflows. As long as the search key that is entered is part of the language key (in English), it's fine. Any other time, it's not.
So this should be addressed more generally in Joomla core.

the same might be true for workflows but searching there will be used far less often.

the same might be true for workflows but searching there will be used far less often.

Definitely.