Another DataGrid (ObservableCollection) Filtering Method
You can refactor this into LINQ query for (arguably) better readability.

AllCompanies.Where(c =&gt; CompanyMatchesFilters(c))
            .Where(c =&gt; CleanseText(company.Name).Contains(searchText)
                     || CleanseText(company.Town).Contains(searchText) 
                     || CleanseText(company.Postcode).Contains(searchText))
            .Take(25);


As for performance - nothing in the code you've shown strikes me as potential performance bottleneck. You will probably have to run a profiler to pinpoint it. One thing in particular you might want to look at is what triggers the search and how often it is executed. For example, if I enter 10 chars in search box, do I search 1 or 10 times? While the filtering logic looks fairly lightweight, the performance implications of recreating 25 item templates in UI on every keystroke can be severe (depending on how complex the DataTemplate is). Rx has some nice extensions that might help in throttling UI events.

P.S. Whats the point of removing all meaningful characters in CleanseText? What characters are you interested in then? This is extremely unclear, you should document that portion of your code.