It says Lorely of the Elite Four has gone missing... what do I do?

You need to find her. She's in the Lost Cave.

I caught all the legenary birds and she came back... But it most likely wasn't that.

What you have to do is travel to Four Island, then go to Icefall Cave and find Lorelei. Then when you find her you will battle a little rocket and she will go home...then go talk to Celio on One Island.

Get the Ruby at Mt. Ember. Go to Six Island to the Dotted Hole and use Cut. Navigate through the place to get the Sapphire. Go to Five Island defeat the rockets and then she will have returned... Oh yeah do it in that order or you will not get both passwords for the hideout

You need to get the rainbow pass and then go to Four Island and from there go to Ice Fall Caves and travel threw it. There you will get a HM call Waterfall and use it so you can travel up the waterfall at the beginning of the cave, then go down the hole with the stairs in it, GO UP DON'T GO DOWN!!!!!!!!!!!!!!!!!!!!!!!!!!!!

Because if you go down you have to go back up the Waterfall, so from there go in to the hole and there is Loreli and you will have to fight a rocket, then she gives a speach and you still have to do some more things but that it from what I can remember to get her found.