SQL - Slow Like or Between

Note: Cross posted because it's SQL in RPG, but I think it's just an SQL
issue.

A continuation of an email that I sent a couple of days ago, and got some
good feedback. I'm returning a result set to RPG or PHP via a stored
procedure.

On further analysis, I need to provide a starting point for record access.
I was using static SQL and a Between clause for each of 10 fields between
*LOVAL and *HIVAL. Takes too long to run...like 60 seconds over an 800K
record file.

I created individual indexes (EVI's) over each of the 10 possible columns.

Tried static SQL with a technique like this: Where :xxvnda1 in (' ',
IMVNDA) And.... Still too slow.

Tried dynamic SQL by creating the statement using equal, like this:
SQLStmt = SQLStmt + cBlank + 'IMVNDA =' + cBlank + cQuote + xxvnda1 +
cQuote; Much faster when looking for an equal, but doesn't return records
that don't match exactly.

Tried dynamic SQL using Like, and it's as slow as the initial static
technique.

I'm going to try dynamic SQL using a Between clause, but not as far as
*LOVAL and *HIVAL, and only including the columns I want to search in the
Where clause. I'm not anticipating good results though.

Question (finally): What's the best technique for an SQL-based search where
I return a result set from a search of multiple fields?

Thanks for any ideas.