Complex queries do not work when searching within Facebook's public feed

Originally reported by XComp on GitHub:

when I want to search within Facebook's public feed using FeedTemplate.searchPublicFeed(String, int, int) it works fine, when there is only one keyword within the query. Facebook supports also logical operators like AND (which actually is represented by a space or +), OR (which is represented by a pipe framed by spaces) and quotes.
Using those operators within a query passed through searchPublicFeed(String, int, int) wouldn't return any results. The reason for that is that internally the query is built and encoded. Since the search terms are also encoded, Facebook is unable to interpret them correctly. This is the same issue when using special characters like German Umlaute.
A solution might be to disable encoding for the search terms. But this seems to be a dirty hack, doesn't it?