Since neither of you can can imagine why anybody would need to search a true/false value, I'll show you a working example.
http://www.csea.org/search/findanea.asp
This search works by looking for whether or not the associated column in the database (a standard bit) is a 1 or a 0. Simple bit logic. True or False. In laymans terms: Find me a list of people that are in the zip code I provide and that are proficient in these things I have checked. Were it not possible to search for the boolean values, this entire operation would suffer a performance loss. Even if I were to have designed this to use a varchar as the data type in the column and stored the values as either 1/0 or true/false, the functionality would still have been the same. We search based upon what is in the checkboxes. Those checkboxes could very easily be replaced by a dropdown list, and it would still work the same way. Find me a list of people that are in the zip code that I provide and are proficient in this thing. I have another, similar search in the members area of the website.
You, as the developers, have severely hampered your product by leaving the ability to search the True/False fields out of the module. You are the ones that control how the data is stored, so any complexity that is present is added by you and you alone, and there is no need for this to be a complex thing. You are the ones that control what options are in the dropdowns and how they work.
I'll try your fix, Stefan. It's only a bandage on the real problem, though.