While running the 7101-upgrade on a 70k-sized database I noticed that there is no index on redhen_engagement.contact_id after creating that index the migration took only one second (as opposed to several minutes).
I had a look at the hook_schema implementation that define foreign keys - but even newly installed drupal sites missed those foreign keys (and therefore indexes on the affected columns). That's when I finally found: http://drupal.org/node/911352 .
In short: D7 simply ignores foreign keys defined in hook_schema(). All foreign keys need to be declared explicitly in hook_install() using ALTER TABLE.