Your first task is to detect the foreign keys that have missing indexes. I've created the following query for SQL Server 2005. I have to test it some more to be sure it covers everything but on my little test database it seems to work fine. This is obviously a starting point and you can extend the query quite easily. I'm not checking if the index is too wide to be considered yet, but obviously none of you guys have such wide indexes right?
I'll give it a try on a bigger database tomorrow since it's getting kind of late now ;-)
SELECT fk.Name as 'ForeignKey', OBJECT_NAME(fk.parent_object_id) as 'ChildTable',
OBJECT_NAME(fk.referenced_object_id) as 'ParentTable', c.Name as 'Column', i.Name as 'ValidIndex'
FROM sys.foreign_keys fk
INNER JOIN sys.foreign_key_columns fkc ON fk.object_id = fkc.constraint_object_id
INNER JOIN sys.columns c ON c.object_id = fk.parent_object_id AND c.column_id = fkc.parent_column_id
LEFT OUTER JOIN sys.index_columns ic ON ic.object_id = fk.parent_object_id AND c.column_id = ic.column_id AND ic.index_column_id = 1
LEFT OUTER JOIN sys.indexes i ON i.object_id = ic.object_id AND i.index_id = ic.index_id
ORDER BY ChildTable, ParentTable