Challenge to all DBAs

I have a challenge for all DBAs. I am getting INCONSISTENT TIMINGS for Querry Results from a SQL Server 2000 Standard Edition on a HP Proliant 2 CPU Server with 4 GB RAM and SCSI DrivAFAe.

Our Database is 72 million records and have 8 columns. Most of them are indexed, which are used in the "Where…" clause. In addition to independent indexes, we also have a covering index for 3 most frequently searched fields.

My challenge is that out of the 7000 odd queries that hit the server with various search conditions in a Week, 5% of the queries return result in less than a minute.

The same query at a different Time or with a different Value, returns results inconsistently. For e.g. searching FirstName = "Anna"; LastName = "Williams" returns result in 0.01 sec. Searching for FirstName "Benjamin"; LastName = "Watson" returns in 5 minutes.

Any kind of help is welcome and will be highly appreciated.

- Santy

san.rely@.gmail.com
Note: Edited to fix white on white font.

Run the queries in query analyzer, have it show the execution plan, and look and see what is different, if anything.