No matter what game you play, Mythical Pokémon are always the hardest Pokémon to find and in Pokémon Picross, it is no different. All Mythical Pokémon are in the game but have a special mechanism tied to their appearance. They won't just appear in any old level, but rather unlock through the passage of time.
This isn't the time that you play the game, but the time that has passed since you began playing and then from your last Mythical Pokémon encounter. After certain amount of time has passed, Professor Tetra will come up and say that there is news of a Pokémon having appeared nearby and will guide you to the location. You have a time limit for when the stage is playable from when you get told about the Mythical Pokémon. If you miss this time limit, you'll need to wait for it to come back, which can be a very long time to wait.
If you do complete the puzzle, however, you will be able to play the stage as often as you like from then on.
Do note that changing the clock will inhibit your ability to find these Pokémon. Also, after you have completed the Alt World, the Mythicals will start appearing with no space between them