I've had this bug for a while but never wrote it down until now.
On my Android side, I have DAVx5 set up to synchronize contacts via WebDAV. They all appear in the list, however when I am in the phone dialer and type in a person's name, it literally never returns the results I expect.
So, for example, if I have a contact named Zirgo Fleham, and I type "zirgo," it will not show the contact in the search results. Oftentimes, it returns names that do not even have the search string in them.
This bug only happens in the Phone dialer, however. If I search in the Contacts app, then things work as expected.
I downloaded third-party dialer apps and they don't have this problem, only the default Dialer.
I just got a replacement Gemini and the bug exists on this new unit. I'm not running 8.1 though since I want to keep my root setup for now.