All right, matty asked me to build a script for this so here it is. Open the search window through the script menu or with the /contactsearch command. Type in the query to search for and hit Search! Double-click a contact in the list of results to open a conversation with him/her. Yes, it's as simple as that!
Currently, the script is limited to searching name or personal message and the words in the query have to follow each other exactly in the matches. The search is case-insensitive, so ABC is equal to abc, aBc, AbC,... And last but not least, the results list is sortable!
Enjoy!