One solution would be for the client to combine all the addresses they are interested in into a single bloom filter and send that to the server.

<snip extra ideas>

Hey Joseph,

All those ideas are ones we had years ago and they are implemented in the current Bitcoin protocol.

The trick, as you may know, is this bit: 

The client would also need to be fairly clever

It turns out making a sufficiently clever client to fool even advanced observers is a lot of programming work, assuming you wish for the Ultimate Solution which lets you allocate a desired quantity of bandwidth and then use it to maximize privacy.