Intel SGX is only answer at the moment. The Signal messenger uses it, do address book matching is private. It requires the user to trust the server hardware vendor (Intel) instead of also the cloud provider.
That would not stop the Bing query matcher (or indeed the Signal address book matcher) from being able to look at the contents of its own secure enclave.
The trick is that every user uploads his own matcher. The server only sees encrypted matchers, feeds them data and returns the encrypted results. You as a user decrypt your results and nobody (except Intel) was able to see them.