Kanto introduced Moltres, Zapdos, Articuno, Mew, and Mewtwo. Johto introduced Raikou, Entei, Suicune, Lugia, Celebi, and Ho-Oh. Hoenn introduced Regirock, Regice, Registeel, Latias, Latios, Kyogre, Groudon, Rayquaza, Jirachi, and Deoxys. And now we have Sinnoh, which introduced Regigigas, Giratina, Darkrai, Arceus, Mesprit, Uxie, Azelf, Dialga, Palkia, Manaphy, Phione, Cresselia, and Heatran.
Kanto and Johto are next to one another, Hoenn elsewhere, and Sinnoh even farther, probably in the opposite direction.
We can discount Deoxys and Mewtwo as far as legends go. Deoxys is just an alien virus that mutated, and Mewtwo was created by humans. They're just incredibly strong Pokémon, and nothing more.
Zapdos, Moltres, and Articuno represent the forces of lightning, fire, and ice. As Prof. Oak stated in The Power of One, an electrically-charged steam current has the power to flood the planet. This is basically what the "Beast of the Sea" was, caused by an imbalance of power between the trinity of forces. Lugia, having ocean-related powers in combination with being a Psychic type, allowed it to calm the birds. Not on its own, of course; Ash needed to get the orbs from each island and place them in a single shrine. I suspect that these orbs were charged with the elemental powers of the respective birds, and the sound waves from Melody's ocarina or Lugia's cry caused the radiation from those orbs to harmonize, which in turn would harmonize the birds themselves, restoring the balance and "calming the 'Beast of the Sea'". Such a form of radiation would only affect Articuno, Moltres, and Zapdos in this way. It would be just like light from a flashlight to anyone else.
In Ecruteak City, we learn that Lugia and Ho-Oh lived there atop twin towers in ancient times, but human greed and lust for power chased them away. If I remember correctly, the Tin Tower is where Lugia lived, and the Brass Tower (now the Burnt Tower) was Ho-Oh's perch. Lugia probably evolved (not in the Pokémon way) to adapt to the ocean, thus why you find it in the Whirl Islands. Ho-Oh probably decided to return to the Tin Tower, since it was the only tower standing and sensed your kindness.
Again in Ecruteak, you learn that Ho-Oh has a connection to Entei, Raikou, and especially Suicune. It seems to me that the legendary dog trio are judges, racing across the land not just because their power is incredible (and yet they're all BL/OU? What the hell?), but also because they were watching us humans. Then you come along, capture/defeat all three, and Ho-Oh understands that humans aren't beyond redemption, and thus flies to Tin Tower and awaits you.
Speaking of Suicune, there's a connection with the Unown here. They never were considered like this before, but perhaps Unown can be a legendary Pokémon? Also, if you've seen Spell of the Unown, you know that the Unown come from an alternate dimension... Perhaps the same dimension Giratina hails from? Maybe the Unown were created so that humans could better understand Pokémon simply by spelling certain things out.
Mew, being the ancestor of all Pokémon, can learn every move that can be taught by humans or learned on its own. It can also learn every other move, but without a method, there's no way to demonstrate this. Mewtwo was created by humans using Mew's DNA, but because they capitalized on power, Mewtwo lost the ability to learn all moves like Mew can.
In ancient times, the Hoenn Region's legends tell of a Pokémon who created oceans and a Pokémon who carved mountains. Kyogre and Groudon, the "weather ubers", are these, and they apparently conflict in every way. Apparently, the Red and Blue Orbs allow the wielder's heart to speak to, perhaps control, these Pokémon. Team Aqua's leader's heart was corrupted by a lust for power, thus driving Kyogre berserk (as seen in the anime). Pikachu's heart was pure, so Groudon was able to stop Kyogre.
However, it can also be said that Kyogre and Groudon can reject the Orbs' power and return to the Cave of Origin, their apparent birthplace. As shown in Pokémon Emerald Version, Rayquaza can force both Kyogre and Groudon into a stalemate and send them away, which is probably why the Air Lock ability is only Rayquaza's. Whenever Groudon and Kyogre meet, a huge battle between them ensues. Apparently, this is not because they hate one another, but because such a clash needs to happen in a certain spot to create a certain environment.
Rayquaza is known as the Sky High Pokémon, and rightly so, for it makes its home beyond human eyesight in the ozone layer. This is why Rayquaza was the first to encounter Deoxys, who mutated because of the ozone it passed through. Rayquaza recognized Deoxys as the alien virus it was, and thus attacked it. Thinking that the virus was eliminated, Rayquaza returned to the ozone layer. Years later, Deoxys reawoke and started looking for the other Deoxys. Rayquaza sensed this and sped off in an intercept course, making sure to eradicate the virus this time for good. However, when a certain city's security system goes haywire, it's the twin Deoxys who defend Rayquaza. It's in this moment that Rayquaza realizes the mutation wasn't just a physical one, and from human kindness, both Deoxys have learned much. Rayquaza ceases its mission and returns to the sky, and both Deoxys, knowing they don't belong but taking the memories with them, return to space.
Celebi, the Time Travel Pokémon and guardian of the forest, is said not to appear in war-torn times. Also, in Japan, Pokémon Gold, Silver, and Crystal Versions had a side quest involving the G.S. Ball (which appeared in the anime as well). The player would take the G.S. Ball to the shrine in the Ilex Forest in order to meet Celebi. With this information, it can be said that the G.S. Ball can only be opened by someone pure of heart in a time of peace. Kurt, the Apricorn Ball maker, couldn't even dent the G.S. Ball. That's not to say he's not pure of heart, but it does mean that perhaps, like with Lugia's legend, there was a chosen person to open the G.S. Ball. Also, in Pokémon Colosseum, the Time Flute calls Celebi to fully purify a Shadow Pokémon at the Relic Stone in Agate Village. Celebi does this by apparently combining its time travel and psychic abilities to make the Pokémon remember its happiest moments, as well as to see what you've done to help the world become a better place. You've noticed that the Relic Stone has a circular hole in the top, right? Perhaps the G.S. Ball could also be used here?
Jirachi awakens once for a week every millennium. I'd hate to take a nap for that long only to be awake for a week. Anyway, Jirachi doesn't really relate to any other Pokémon, it's just there for you to stick a note on and cry since you most likely won't live long enough to see the wish fulfilled.
Heatran, the volcanic Pokémon found in Stark Mountain, I don't really know much about. The only possible connection I can think of right now is to Entei, who makes volcanoes erupt by barking. The Pokédex doesn't show any connection, but there are people in Fight Area and Survival Area that talk about Heatran. I'll look them up later.
Latios and Latias roam the Hoenn Region, apparently in a guardianship role. This is especially true in Pokémon Heroes, when Altomare is attacked by a pair of agents from Team Rocket. They apparently have no connection to others.
Shaymin is apparently just a guardian of flowers and nature, who appears only to those who are truly thankful towards Pokémon and nature for their beauty and mutual uses.
Darkrai and Cresselia appear to oppose one another in the same way light and darkness do. Darkrai's Dark Void traps someone into sleep, while Bad Dreams turns dreams to nightmares. However, this state can be reversed by the Lunar Wing, which is apparently a feather from Cresselia's pink curves in spite of its own green color. I assume that the Lunar Wing becomes green after dropping from Cresselia's body, much like a branch will become brown in the center instead of green because it's no longer attached to the tree it came from. However, Cresselia and Darkrai also work together, being essentially Moon and Shadow, which always go hand-in-hand anyway.
Regigigas is a very interesting Pokémon, because it's bigger than a blue whale (look at the trailer for the movie after Dialga VS Palkia VS Darkrai). Now look at it in Pokémon Battle Revolution, and Dialga's bigger. What the hell? Well, anyway, Regigigas apparently worked together with Groudon, or at least cleaned up its mess, pulling the continents together. This is probably how Regirock was formed, what with all that rock from everywhere being thrown around. Regice was probably formed from the earliest polar ice caps' ice, and Registeel was probably made from metal found in a meteorite that Regigigas snatched out of the sky as it fell. Regigigas would shape these three Pokémon, give them life, and put them in what would become Hoenn as totems, or perhaps guardians (see Lucario and the Mystery of Mew). By capturing all three "totems", bringing them to Sinnoh, and going down into the Snowpoint Temple, one could reawaken Regigigas. I'm sure the next movie will shed more light on Regigigas, Shaymin, and Giratina. Until then, we can only speculate on this one.
Giratina, the only Ghost/Dragon Pokémon to exist, who lives in an alternate dimension. This one's really interesting to me, because it's mainly defensive. I'd guess then that Giratina acts in the Pokémon world much like Cerberus would in the Greek mythological version of the Underworld. It's a guardian who keeps the dead and the living seperate. It can apparently disappear into darkness at will, just like Darkrai can, given the Shadow Force move only it can learn. There appears to be a relation to Shaymin and Regigigas as well.
That leaves Arceus, Uxie, Mesprit, Azelf, Palkia, and Dialga. Sinnoh's legends state that an Egg appeared in a vortex of chaos, and from it Arceus was born. Arceus created Dialga and Palkia to create time and space, then created Azelf, Uxie, and Mesprit to create emotion, will, and knowledge. Arceus then went to sleep, apparently in the Hall of Origin, an area in Sinnoh directly above the Spear Pillar where dimensions would shift, allowing Arceus to appear.
With the creation of time, space, will, knowledge, and emotion, it seems to me that these five would create Regigigas (who would in turn create Regirock, Regice, and Registeel as guardians), Groudon, Rayquaza, and Kyogre (who would shape the pieces of the world and guard them, with Regigigas putting those pieces together). To keep the balance, Dialga and Palkia would leave for the alternate dimension with Arceus, while Mesprit, Uxie, and Azelf would sleep in the Sinnoh Region. Arceus apparently left Plates behind, telling its story so as not to be forgotten. If that's correct, then it's only natural that Arceus has the Multitype ability. Because those Plates came from Arceus, putting them back on Arceus would unlock a change. And yes, Arceus would have to be a "god" in order to create a universe and other "gods" to create other forces and guard them.
Since no world could have existed before time and space did, it's perfectly possible that Mew was the first Pokémon who actually originated from this planet, and from Mew, the rest of the Pokémon not mentioned in this post.
That's my take on it.
