For posterity, I think I found an answer:
Using the Parameterized Search API, I can query this endpoint:
with this POST body:
"q" : "Account",
"where":"External_ID__c = 'Account.050' or External_ID__c = 'Account.001' or External_ID__c = 'Account.12345'"}],
"q" : "Account" : this is the search term - all my records have an text field with an external identifier where the prefix is 'Account'...
(FYI, this query field does not appear to be able to take arrays as a search term. It also has to be longer than 1 character.)
The way I search for multiple specific values is to find them all with a generic search value in "q", and then get specific in the WHERE clause with ORs.
I don't know how large by POST body can be, or how large the "Where" clause can be... but this is progress.