You are quite right, it is a question of scale and, yes, I am joining this table with several other tables.

The core driving table (that has the columns for which I have criteria) is a very large table. If I use 'SMITH' in my query, it takes f.o.r.e.v.e.r (100+ seconds), if I use 'FUZ', it returns in 3 seconds.

I apologize, but I can't post the query. Don't you think the bottom line is the issue of selectivity?

Would Oracle Text help here?