Эффективный поиск

Использовать AutoComplete. Например поставить комбобоксу myCMB.AutoCompleteMode = AutoCompleteMode.SuggestAppend и AutoCompleteSource = AutoCompleteSource.CustomSource. Это позволит автоматически сортировать выпадающий список.

В Wpf я делал так: Xaml:

 <Label Content="Searched text:"/>
                <TextBox Grid.Column="1" Text="{Binding FilterString, UpdateSourceTrigger=PropertyChanged}"  />
            </Grid>
            <DataGrid Grid.Row="1" ItemsSource="{Binding Path=MyList, Mode=OneWay, UpdateSourceTrigger=PropertyChanged}">
                <DataGrid.Columns>
                    <DataGridTextColumn Header="Name" Binding="{Binding Name, Mode=OneWay}" Width="40*" SortDirection="Ascending"/>
                    <DataGridTextColumn Header="Version" Binding="{Binding Version, Mode=OneWay}" Width="10*" />                    
                </DataGrid.Columns>
            </DataGrid>

Code:

    private ICollectionView _myList;
     public ICollectionView MyList
     {
        get { return _myList; }
        set
        {
           _myList = value;
           NotifyPropertyChanged("MyList");
        }
     }
    private string _filterString = string.Empty;
    public bool FilterTask(object value)
    {
       var entry = value as MyListModel;
       return entry != null && (string.IsNullOrEmpty(_filterString) || 
entry.DisplayName.ToLower().Contains(_filterString.ToLower()));
    }           
    public string FilterString
    {
      get { return _filterString; }
      set
      {
          _filterString = value;
           NotifyPropertyChanged("FilterString");
           if (_myList != null)
              _myList.Refresh();
       }
    }        

работает с 3000 записями быстро. Тут фильтром выступает текст бокс и фильтрует таблицу, но вы можете изменить реализацию под себя.

Ах да, в конструкторе при присваивании коллекции значений нужно указать:

MyList.Filter = FilterTask;