I recently deleted four contact filters. Afterward, the contacts search feature for contacts, SMS, and phone log does not work. When I begin typing a name, the search results indicate "No Contacts". This is not true.
There is one catch, the search feature in Contacts does work for my BB Messenger Contacts but not for any other contacts.
It sounds like some of the software may have become corrupted. I would try to wipe the data from your device and then reload or Operating System (OS) software. To do this, follow the instructions found at http://crackberry.com/blackberry-101-lecture-12-how-reload-operating-system-nuked-blackberry and your contacts should start working like it is supposed to work.