According to this one strat guide I just checked it says the red mail is in the guardia castle in 1000 A.D. and the red vest is there also in 600 A.D. Maybe they just moved the box. After all it is a busy castle. I think it is in one of those rooms when climbing and decending stairs...maybe.
