For Mada's Locket, you need to have beaten the game first, then check the other picture in the fairy palace(it's north of Zenithian tower). You went through the left one as part of progressing through the game, so the right one is the other. Since you have beaten the game(and saved), the picture here changed. There's more to it, but I'll leave that up to you to go talk to the people inside until you get stuck again.
Look, I ain't some tasty-lookin' burrito sittin' on the side of the road, but you gotta take me with you! HOLY ****! MY ASS TURNED TO JELL-O! - Diorte