The computational assumption is a 2-message scheme that is PIR with
respect to the client<-server message and can easily handle databases in
which the number of entries is small but the entries themselves are large.
I'll describe a candidate for that, followed by how it can be applied for your use-case.
"s" is not really related to "Server"; I'm just following the paper that I link to for the sort-of-PIR scheme.
The suggested sort-of-PIR scheme is the following:
User U generates an RSA key-pair with modulus N, sends the public key
to the server, and stores the key-pair, with the private-key kept private.
For a desired index i out of B possible entries each of which are less than N^s,
the user sends the server a list of B ciphertexts such that the i-th is
an encryption of 1 and the others are all encryptions of 0 (page 8).
The server computes its response as the product modulo N^(s+1) of the
[corresponding database entry]-th powers of the ciphertexts in the list.
That response will decrypt (as described in that link,
not with the usual RSA decryption) to the i-th entry of the database.
On key-pair reuse:
Whether or not key-pairs can be reused is a non-trivial issue.
Since the encryption is public-key, an adversary could generate the ciphertext tuples
on its own, so that can only be a problem insofar as a server chooses its responses
maliciously and [can learn and/or wants to manipulate] the user's outputs.
Since the encryption is additively homomorphic, the flipside of that coin is that it is additively malleable.
However, I do not see any attacks on key-pair reuse that do not follow from that malleability
and/or replaying ciphertexts. $\:$ Thus, I think this is just a question of security vs efficiency.
The simplest way to apply the sort-of-PIR scheme for your use-case:
Either a base B was hard-coded into the protocol, or the user chooses it and sends it to the server for each protocol execution. $\:$ The user does whatever may be necessary regarding (the) key-pair(s), converts the id to base B, generates a list of sort-of-PIR initial messages with desired entries equal to the corresponding base-B digits, and sends that to the server. $\:$ The server sorts the set of ids and might also want to explicitly convert them to base B. $\:$ (Those might be doable offline, and even if it doesn't do the latter, "ids starting with" still refers to their base-B representation.) $\:$ Starting with partialid equal to the empty string, the server recursively does the following: if there are no ids starting with partialid then return 0, else if some id is equal to partialid return 1, else get the B results returned by running this procedure
on the B ways to extend partialid by one base-B digit, use those as the database for the sort-of-PIR
with the User's initial message corresponding to the length of partialid, and return the response given
by the sort-of-PIR scheme. $\:$ The server then sends the result of that recursive procedure to the client.
Finally, the client gets its output by decrypting with its private key(s in order)
a number of times equal to the length of (2^256)-1 in base B.
One can use a mixed-radix system. $\:$ One can skip [Client's initial and Server's final] one or more uses of the sort-of-PIR scheme, to trade off client<-server communication for client->server communication.
One should notice that the simple way, even with the modifications mentioned in the previous two sentences, directly supports actually retrieving records that are smaller than the (smallest) modulus,
by returning the record rather than returning 1 in the recursive procedure.
In fact, it can be used to retrieve longer records, by just using a higher length parameter.
One can trade that off for slightly improved efficiency, as follows: use the record-retrieving procedure
on slightly truncated ids, where the records are the sets of suffixes for those truncated ids.
One can do better at the cost of a small failure probability by using non-cryptographic
hashes of ids with separate chaining instead of slightly truncated ids with sets of suffixes.
In the massive-database very-small-error region, one may be able to improve on the previous sentence by using [truncations of k-wise almost-independent permutations of ids] with compressed
sparse bit arrays instead of non-cryptographic hashes of ids with separate chaining.
Queries containing a list of record ids:
One can apply Rijndael to the ids before doing anything else with them and split both the transformed list and the transformed database. $\:$ (That reduces the remaining range of ids in each part.)
For large enough lists, one might be confident-enough that the transformed ids from the list will be distributed uniformly-enough to allow one to most-of-the-time make not-much-more than that many queries to each part. $\:$ For very large lists, the effect of the reduction in the range of ids in each part might overcome however many more-than-average queries are needed to each part. $\:$ It may be worthwhile for the Users to have a small probability of unnecessarily moving queries between parts, as an attempt to hide when Rijndael happened to move too many of the actual ids they're interested in into the same part.
The thing I was wrong about in my "answer tomorrow" comment:
If you allow a(n exponentially) small probability of the user outputting failure, then the growth rates of communication complexity and client's computation with respect to the number of elements are both really hard to figure out, although I'm pretty sure they're at least logarithmic and at most polylogarithmic.
(That holds even if you require that the server be able to detect failure on its own.)