Just a random thought... are there any databases out there which profile all the queries that are run and are capable of auto-creating or suggesting indexes that would be worthwhile creating?

 

Seems like they already do much of this work, and it wouldn't take a great deal to store any relevant info, analyse it every so often, and offer suggestions for indexes which could be implemented and tested for improvements.

 

Is there anything I'm missing for why this isn't done?

Dunno about others, but Microsoft SQL Server has the Database Engine Tuning Advisor which does exactly what you describe. You set it running for a while, or give it a sample workload, and it suggests indexes and statistics to create.