>I do not understand this situation. All fields used in the query are indexed. I also have some combo index to satisfy the execution plan. The result returns one record. However, based on the conditions, it can take between one and 40 seconds. What else could be a factor?

There could be zillion of factors. The current work load on the server, which plan the optimizer chose for the query, how many I/O operations (page reads) were involved in the query, etc.

Although the difference in numbers is too drastic.

Take a look at this blog post Glenn Berry Query Optimization Diagnostic Queries
and try running them to analyze the situation.

Also, are you using ad-hoc query or stored procedure with the compiled plan?