Before you fight the Cloud of Darkness for the second time, do you see the scene where the four Warriors of Darkness run into the Cloud of Darkness and die? If not, you probably haven't defeated all four of them. You should have fought Cerberus, Ahriman, Twin Dragon and Echidna. Otherwise I would say your game is bugged but I don't see how unless all that junk surrounding the dupe trick isn't false, although I am fairly sure it is.
