Cleaning up orphaned metadata in information_schema
The way that I found to "solve" this problem is fairly annoying, but there is a script that handles it.

Essentially, you need the ibdata1 and ib_logfile* files to go away (they contain the mappings of foreign keys, among other things). The only safe way to do this is to export all of your databases, stop mysql, remove the files, start mysql, and then import the files.

The script that helps solve this problem is https://github.com/uberhacker/shrink-ibdata1, even though the stated purpose of this script is different, it does solve the problem.