MyContacs is the application I created to try to "improve" the standard contacts application. It is a qt application and includes a widget for quick access to your contacts on the desktop and soon will allow you to just say "contact person X" and the application will figure out the best way based on your preferences, connection status and contact information.

For my application to route calls to yours it is all that I need. I would also suggest that you don't need to develop yet another contact search/select interface, you could just use mine. There would be a dbus interface for you to tell my application that the user wants to pick a contact phone and after he does, mine will just call the "callNumber" method with the selected phone number. Optionally I would suggest that you add one more argument for callnumber so I can pass the contact name and you can display it as well.

You can see all this is in action by installing mycontacts and fastsms. You will find the link to the mycontacts thread on my signature bellow. If you like the idea when can discuss the details (service name, ...)