I did some more testing and I think I may have found the potential cause. I noticed that in some cases the string values in the company name field contain the name of the city where the company is located, and the city name is separated from the company name by a comma or a dash. I started to suspect that these special characters could be problematic.
I duplicated the company name field and got rid of all special characters by editing aliases. And after that filtering started working! Furthermore, as soon as I cleared the aliases, filtering did not work any more. Seems obvious to me that the field values are somehow causing the problem, but I haven't seen this documented anywhere, so can anyone confirm my findings?