Wow, I didn`t think this would get many replies at all. oo;;
Anyways. It seems to be that Regigigas is one of the most powerful Pokèmon in existence. Assuming that it is manmade, as the other three golems are, this Pokèmon would need to have been made out of something extraordinarily powerful. I`d say there`s three options here:
1) A space meteor that came into contact with the planet`s natural elements.
2) A fragment of the life-making essence that is Aruseus, crafted by humans.
3) A human-made combination of several elements found in nature, perhaps combined with some kind of mystical stone, to create Regigigas.
Now, regarding the whole debate over this Pokèmon moving a continent, you are forgetting the context in which the Pokèdex puts it: "A legend has been passed down". An oral legend of old times, probably. In such tall tales, the contents are usually changed every time a person tells the story, ending in a warped version of the original. "...that this POKèMON moved a continent by pulling it with a rope" could simply mean that Regigigas is very strong and very old, and probably has some connection to the higher beings of Pokèmon (Aruseus, Diaruga, Parukia, the Fairy Trio), who it served by shaping the tectonic plates of the world in a distant past.
It is plausible that ancient humans, marveled with this Pokèmon`s power, used part of whatever-it-is-made-of and used them with the common elements of Ice, Rock and Steel to create three lesser, yet still very powerful servants for their own use. And yet, these Pokèmon were even more powerful than they expected, and humans, as is in their nature, became afraid of what they couldn`t control. They quickly used their own Pokèmon to seal their once faithful servants away, and then went straight to the source--Regigigas, who with much trouble they put to sleep as well. The reason why it is in another region could be because the lesser Regis were transported to serve the humans of Hoenn, the continental divide separated a once great landmass into Hoenn and Sinnoh, or they had to seal it in another place to stop it from interfering with the spells cast on the other, weaker golems. Remember that the Regis are inherently pacific, so they could have easily been lured to their own tombs. This is also why Regigigas has the Slow Start ability--it has been sealed for eons, and anyone would be a bit sluggish after that.
...Yeah.