Hey @babeach,
I don't know if you're still looking for a solution for this.. the problem is that you've got complex Text Fields - when you do a filter on this, it looks at the literal text (so, the formula) rather than the lookup values.
I've recently created a gallery where multiple items within it are searchable - the solution was to create multiple invisible labels where the Text is just ThisItem.Thingy then to have the initial search filter run an Or() logic search of those items.
I've attached pic of a few of the fields I set up (some require that you use .Value) and below is the code solution:
SortByColumns(
Filter('Issue and Actions',
(
Or(
StartsWith(Title, TextSearchBox1.Text),
StartsWith(Owner.DisplayName, TextSearchBox1.Text),
StartsWith(Contract.Value, TextSearchBox1.Text),
StartsWith(TypeOfIssue.Value, TextSearchBox1.Text),
StartsWith(Text(IssueNo), TextSearchBox1.Text)
)
)
),
"Title",
If(SortDescending1, Descending, Ascending)
)

*Edit*
In order to delegate the searches back to Sharepoint instead of limiting your results for anything with .Value or .Text columns:
Create a new Text column in SharePoint, Call it TheReferredThingActualValue
Refresh the data source in your app, add that column as a field within the gallery, make it invisible.
In any of your edit/new screens have your app fill the Default value of the Textbox of TheReferredThing Card with Text(TheReferredThing.Value) during every edit/new item (or go into sharepoint and retrospectively copy/paste the text value for all historic items OR create a Flow that extracts the Thing.Value and populates the new Text Column with those values).
Once those fields are filled, you can change your filter to:
Filter('Issue and Actions',
(
Or(
StartsWith(Title, TextSearchBox1.Text),
StartsWith(OwnerDisplayNameActualValue, TextSearchBox1.Text),
StartsWith(ContractActualValue, TextSearchBox1.Text),
StartsWith(TypeOfIssueActualValue, TextSearchBox1.Text),
StartsWith(Text(IssueNo), TextSearchBox1.Text)
)
)
Which will then be Delegable