How to resolve "InnoDB data dictionary has tablespace id N"
Creating a table in a new database with the same name as the "missing" table, and copying the corresponding file was the solution.

Hopefully someone can post a better solution, but here's the hack I put together to sort this out for myself. Really ugly, but still might benefit someone in the future.

grep "InnoDB: Error: table " /var/log/mysql/error.log
  | grep 141028 # Today's date
  | grep [problematic-database]
  | sort -u
  | awk '{ print $6 }'
  | awk -F/ '{ print $2 }'
  | sed "s/'$//"
  | while read table;
  do
    echo "use temp; create table if not exists $table (random varchar(2))"
    | mysql
    cp -v temp/"$table".frm [problematic-database]/;
    echo "drop table temp.$table; drop table [problematic-database].$table"
    | mysql
  done