We were having similar problems with an application using ASP for a front end, VB6/COM+ in the middle and SQL Server at the back. We finally narrowed it down...

We also use the case statement for dynamic queries. The performance seems very good and is easy to maintain. If you add an option to your search criteria...