We figured out the problem. At some point, support for querying by uid for _allDocuments was removed. We weren't passing in any uid, but removing the unused query parameter solved the problem.
It would have been nice to have a more relevant error message, though.