I've been exploring this issue and found the cause:
In Hibernate 4 FK names were generated thusly (org.hibernate.mapping.Table#createForeignKey(String keyName, List keyColumns, String referencedEntityName, List referencedColumns):

fk.setName( "FK" + uniqueColumnString( keyColumns.iterator(), referencedEntityName ) );

where uniqueColumnString did this:

public String uniqueColumnString(Iterator iterator, String referencedEntityName) {
  int result = 0;
  if ( referencedEntityName != null ) {
    result += referencedEntityName.hashCode();
  }
  while ( iterator.hasNext() ) {
    result += iterator.next().hashCode();
  }
  return ( Integer.toHexString( name.hashCode() ) + Integer.toHexString( result ) ).toUpperCase();
}

Now I'd love to replicate this behaviour for backwards compatibility of FK names in my ImplicitNamingStrategy#determineForeignKeyName(ImplicitForeignKeyNameSource source), but ImplicitForeignKeyNameSource source provides no access to columList Iterator<org.hibernate.mapping.Column> for computing this part:

while ( iterator.hasNext() ) {
  result += iterator.next().hashCode();
}

Without going all out (reflection) or replacing all our FK with new ones - does enyone have any suggestions?