Would you provide the showplan for one of the smaller queries that is taking a long time to run?

Is the table fragmented? What does DBCC SHOWCONTIG say about the table?

In general, it's good to have a clustered index. You're right about the numerous combinations. Is it common to search on a date, maybe a range? That would make a good candidate for the CI. Maybe there's a FK for a very common join? That would also make a good CI.

-Mike