I've just read an interesting post on Jeff Atwood's site, Coding Horror. He questions why database engines can't self-tune tables by adding indexes.

I seem to remember an automatic tuning wizard with SQL 7.0/2000 (not sure about 2005) which you could setup to do this. It would constantly monitor the use of the tables you specify and suggest indexes you could place on the tables. There was an option to automatically apply suggestions. This would do exactly what Jeff wants, and may well be worth a look into.