I have found the best way to determine if a very large table should have additional indexes is to see what is running against that table. If there is a SP that runs frequently and impacts overall performance to the end user then by all means evaluate that procedure to find what index or indexes are needed.

You can use the Database Tuning Advisory but you may find it may impact the overall performance of the machine using it, or at least from my experience. I would most likely evaluate the procedure by getting an estimated execution plan to try to clean up the scanning.

Good luck.

Kurt