This does not sound like a hard problem at all. Just check the query for localizable keywords ( :{KEYWORD} ), and replace that with the word it represents.

So if the query is "in:bin" just convert that to "in:trash" and use that for searching, without the user knowing. Then you also have no problem with switching languages.