外部キーが存在するのに、なぜ「外部キー制約が失敗する」のですか？

これはバグだと思います。MyISAMエンジンはトランザクションではなく、InnoDbはトランザクションであるため、MySQLではInnoDBからMyISAMテーブルを参照するFOREIGNKEYを追加することはできません。

Try:
ALTER TABLE t_timeoff_request ENGINE=InnoDB;