@Salamander94
PowerApps is limited to a maximum record count of 2000 for all datasources.
Options are:
1) Narrow first - If you can narrow your records, you can then search over that. This means that you can perform a narrowing filter with delegable criteria first and then perform your search over that list.
ex. Search(Filter(yourList, delegableCriteria), yourText, yourColumns)
2) Pull all the records from your datasource - this one is painful and performance impacting, but you can initially pull all of the records of your datasource through a series of delegable criteria into a collection and then use the collection as your datasource in your app to search over.
Personally, I rely on #1 the most.
I hope this is helpful for you.