Yes Shiny Umbreon you're right, the legendaries all have catch rates of 3 while Dialga/Palkia have 30. That explains why they're so easy to capture. As for the others... uhh... I think it's luck added to low HP and sleep. :P
In my first file for Pearl, it took me just one Ultra Ball for Palkia, one Ultra Ball for Azelf, about three to five Ultra Balls for Uxie...
Crazy Cresselia was so hard, but I made her sleep and HP really low... She kept running away from me until one time... the Quick Ball made it.
Mesprit? Somewhere between easy and hard focusing more on easy. I made it sleep and gave it really low HP, then used Mean Look on it (this was another encounter) and then used either Dusk or Quick Ball. Now I love catching Pokémon at night since the Dusk Ball will work 4x effectively in caves and at night.
Giratina nearly made me insane, though. How many Dusk Balls did I use on it...? 10?