In theory it seems a "simple" way to achieve arbitrary scale could be to partition the database of notes by pubkey and scale out horizontally. When a request for a set of pubkeys comes in we split up the request and forward to whatever nodes handle which keys.