Hello,
I have enabled the Dataverse search in Power Platform admin center:

I have selected the needed tables in the Dataverse search section in the solution's Overview through 'Manage search index' and I can see 24 columns added to the index of the problematic table.
I have configured the Quick Find View with the 'Find by ...' columns (4 single line of text column and 1 lookup column)
More than 3 days have passed since the last update.
I still do not get any results when I search with the selected custom columns, except from the out of the box Name of the records from the specific table.
Is there anything more that I can check for?