I could build you a custom database in FileMaker that mocks the layout(s) of Apple Address Book / Contacts, and I could move the data from Contacts / iCloud into FileMaker and give you full search ability, including in the Notes.I use Apple Contacts as my searchable "life" database.... Is there a database program out there that has a searchable address book template that is similar in feel and function to Contacts?
For a standalone / single-user requirement, FileMaker Advanced will let me save that file as a self-running database, meaning that you as the end user do not even have to license a single copy of FileMaker to run it! I could even save it as a Windows self-running file if you wanted me to. We could even include import / export scripts for consistently-formatted data, e.g. to and from spreadsheets.
What I cannot really do properly (yet), is then sync that data with iCloud. Working on that.
But if you don't require iCloud sync and wanted to explore a custom self-running database, it would only cost you the time it takes for development to have a knock off Apple Contacts, with all of your data searchable and intact. I or any other competent FileMaker developer would be happy to assist!