You know, Pocket Informant has had this feature for a long time. We have a whole Search View which lets you search ALL fields with begins/contains clauses, using wildcards * and ? as well as filter by category, dates, and by groups of fields.
And yes, we search every single field in Contacts, Tasks, Appointments including notes (its all user configurable). You can also save searches in Custom Views.
Take a look:
http://www.pocketinformant.com/pocketinformant