Oh! I don't even know where Melchoir is...I'll traipse about the Dark Ages until I find this man.
Actually, he's in the Present Day, on the island that's home to friendly monsters IIRC. One of your portals at the End of Time should lead there.
Man, Square needs to release CT on the virtual console. I'm starting to forget stuff again, and I'm not buying a DS again.