Hitting a database of 50,000+ tracks
It doesn't matter how many tracks if the database is indexed properly. You said earlier that you're using OLEDB? That kind of suggests that you're using a sensible database.
I can't remember what upper limit the ARM database has (and it's not as high as I'd have liked), but it never suffered from performance problems doing this. It was fully-indexed on most of the interesting fields.
27 times (exponentially more if more characters are entered)
No, you misunderstand. The ARM software only hits the database for combinations of the first 3 characters. Then it filters the results itself. This was done precisely to avoid the exponential nature of the search. 3 characters seemed like a good tradeoff between hitting the database and doing the filtering in code.