With the introduction of XMLDB a lot of "foreign key" obvious missing indexes have been added to Moodle DB Schema.
So, new sites created under 1.7 will have some more indexes than old sites migrated from previous versions (non XMLDB stuff).
At some moment in HEAD we must add some utility to look for indexes, compare them with the needed by the XMLDB schema and build them as necessary.
This can be achieved by the upgrade script or by some special script somewhere (Health Center) in the Admin Interface.
The script should iterate over all the Moodle XMLDB structures, getting their indexes and looking in DB if they are present (not matter of their name), creating them if necessary.
Only MySQL and PostgreSQL will need this.