Ravi, can you list the indexes on the table? Good chance you have some redundant ones.
My usual indexing strategy in that kind of situation is to tailor indexes for the most important/most common queries and then deal with others on a case-by-case basis, often SQL can manage with indexes that aren't ideal, which for less important queries is probably OK.
Can you also maybe post a couple of example queries? Have you verified that the queries are indeed using the indexes?
Gail Shaw
Microsoft Certified Master: SQL Server, MVP, M.Sc (Comp Sci)
SQL In The Wild: Discussions on DB performance with occasional diversions into recoverability