I'm guessing this is a webserver/hosting issue.

I notice that the "q" parameter to the search handler is the only required query parameter in any rest endpoint in core:
https://codesearch.wmcloud.org/search/?q=self%3A%3APARAM_SOURCE+%3D%3E+%27query%27%2C&files=&excludeFiles=&repos=MediaWiki+core

This means that, if query parameters aren't making it through to the rest api, it is the one most likely to be noticed as not working, because it'll show an error instead of just not returning the expected result.

Query parameters in general seem to work fine on the server. For example, this works:
https://yi.hamichlol.org.il/%D7%91%D7%9F_%D7%94%D7%90_%D7%94%D7%90?action=raw

However, other query parameters to the rest api don't. For example, this:
https://yi.hamichlol.org.il/w/rest.php/v1/page/%D7%91%D7%9F_%D7%94%D7%90_%D7%94%D7%90/history?older_than=255364

Gives the same results as this:
https://yi.hamichlol.org.il/w/rest.php/v1/page/%D7%91%D7%9F_%D7%94%D7%90_%D7%94%D7%90/history

But it should instead be filtering out the newer revisions.

This parameter does work fine on enwiki. Compare these two:
https://en.wikipedia.org/w/rest.php/v1/page/Barack_Obama/history
https://en.wikipedia.org/w/rest.php/v1/page/Barack_Obama/history?older_than=1179071730

And the q parameter works on enwiki as well:
https://en.wikipedia.org/w/rest.php/v1/search/title?q=Barack_Obama

Unfortunately, I'm painfully monolingual, but someone wanted to, they could use my above Barack Obama urls as a pattern to try on an appropriate page on https://yi.wikipedia.org/ , and confirm they work. That'd rule out some language-related edge case (which seems unlikely to be the problem, but I've been wrong before...)

Anyway, I think it is more likely that something is unhappy with the webserver. It has been awhile since I fiddled directly with Apache (I see a server header with value "Apache/2.4.54 (Debian)"), but maybe something is unhappy with RewriteCond/RewriteRule?

I wonder if https://www.mediawiki.org/wiki/Project:Support_desk might be of some help.

Thanks @BPirkle for your detailed comment and useful pointers! I can confirm that parameters are working correctly on yiwiki.

I have asked for help on the support desk, as per your suggestion. But even if it turns out to be a simple configuration issue on my server, I would suggest that the error reporting should somehow be improved. Getting such an obviously false failureCode was extremely frustrating.

Solved! And it was indeed a problematic RewriteRule.

RewriteRule ^.*rest\.php(.*)$ %{DOCUMENT_ROOT}/w/rest.php?title=$1 [L]

had to be changed to

RewriteRule ^.*rest\.php(.*)$ %{DOCUMENT_ROOT}/w/rest.php [L]

Thanks again, @BPirkle, for pointing me in the right direction!