Full encryption of IDs, partial decryption with customer specific key
So lets assume a few things:


just symmetric primitives suffice;
a symmetric key derivation function and single block encrypt with a 64 bit block cipher is sufficiently fast;
the ID's are unique and not related to customers;
we're not afraid of customers sharing ID's;
there is protection against customers simply guessing ID's;


Scheme:


establish a master key $k_m$
derive customer keys and distribute to customers: $k_{c,name} = KDF(k_m, name)$
derive a data key for each ID with index $i$: $k_{id, i} = KDF(k_m, i)$
create and distribute the encrypted array where each entry $C_i = E(k_{id, i}, ID_i)$


Now comes the tricky part:


when a customer wants to get the ID's he sends you the set of indices to the ID's;
you calculate the customer key and a customer specific data key for each entry: $k_{c,name} = KDF(k_m, name)$ and $k_{c,name,i} = KDF(k_{c,name}, i)$
you calculate the difference between the data key and customer specific data key for each entry: $k_{x,i} = XOR(k_{c,name,i}, k_{id, i})$
you send a map consisting of elements $(i, k_{x, i})$ back to the customer
the customer can now perform $k_{id,i} = XOR(k_{c,name,i}, k_{x, i})$ for each entry
and of course calculate $ID_i = D(k_{id, i}, C_i)$