what can a user search on? if they can only search on a few fields and all fields are required then an SP may be a valid choice. let the db do the heavy work
however the user can search on multiple, optional criteria then BLL/DAL would be the way to go. LLBL can account for just about every predicate a db has and you can dynamically form the request.
You may want to consider a typed list over collection though. This way you pull back just the fields you require and not the entire collection. i would think 22,000 records would be too much information for one user to browse through.
You should consider returning the top X number of records. maybe 500 to 1000. You could have an optional search parameter to pull back the top X results and have preset vaules (100, 250, 500, All). When fetching your list/collection use this value for max rows to return. This would also give you a chance to warn the user of large resultsets an abort the search.