I love Apple's solution when it comes to localization, they will search both the non-localized name and the localized name. So if you're looking for Image Capture, you can find it with Transfert d'Image and with Image Capture.
In the case of Gmail, it would mean that you could search both for in:Bin and in:Trash. The only issue would be if someone creates an additional Bin label in a US locale, then in UK, when searching for that label it would also show items in the trash but that's a better trade of I think.