You can pobably just quickly populate an arraylist (or event a listbox) and use it to search things. This is much faster that trying to do it through the grid.
Here is a sample. It implements a fast FindAll. In this sample, a GridDataBoundGrid with 20000 rows can return all occurrences of a string in less than 100 msecs. It does so by copying the column to an arraylist, and using ArrayList.IndexOf to do the searching.