There are two ways that I see.
First, Oblivious Transfer allows a requester to retrieve relevant information (and only relevant information) from the sender without the requester revealing which piece of information they're after. This would allow the Bob to obtain the key that Alice has for Ted, without Alice knowing that Bob is interested in Ted's key. Depending on the scenario, this could be a vulnerability in the case that Bob has the wrong key -- this protocol would allow him to obtain the correct one from Alice.
Second, Secure Computation allows Bob to obtain the value of $f(x,y)$ where $x$ is only known to Bob and $y$ only known to Alice (and $f$ is mutually known). Let's say that Bob knows that Ted's key is stored at position $i$ of Alice's contact list. Then we could have $y=$Alice's contacts, $x=(i,t)$ where $t$ is they key Bob has for Ted. Then $f(x,y)=[[y[i] == t]]$.