I just experienced the same problem as the OP, with all my contacts being iCloud.
Searched for all kinds of keywords - no return of anything.
Then, after ~50 attempts w/ success, search suddenly returned what I was trying to find.
Then, minutes later, again, nothing. No matter what I entered (first/last name, job, note, address, company etc.) nothing was returned by the search.
I logged in to icloud and modified one contact to kick icloud - no success.
I finally rebooted my phone, and it decided to work again.
The official Apple feedback site does not allow for the contacts app to be selected (seriously???!!!???).
Does anyone else know how to report this bug back to Apple - without forever having to perform pointless exercises with their support over the phone first?
Finding contacts ist maybe THE core function of a PHONE. An it does not work properly under iOS15.