I would swear I had been using some option to search for contacts by name (when adding new contact) in the past but can't find anything like this in Telepathy 0.9.0.
Am I missing something?

I'm afraid we've never had such feature, sorry.

You can search for server chat rooms though.