The lookup has to come from your phone, which implicitly discloses you. Encrypting the caller-id symmetrically or asymmetrically wouldn't get privacy, because the receiver would have the decryption key. Hashing it, even with a seed, would be dumb because it's enumerable as you pointed out. But encrypting the entire query does work, because it becomes on a homomorphic search on uniform looking data. So the receiver has no idea what you queried.

That said, research on things like memory access side-channels is thin here. Like if I take a guess and try a query for my guess number, are there timings there that could be exploited because of cache effects? I have no idea, but a lot of PIR schemes have fallen to this.