Masterballs are better for the travelling Pokémon because ... well, they travel. and flee.
I MasterBall'd my Cresselia and used Dark Balls at night on Mesprit*. Dark Balls, Quick Balls (in the first 5 turns), and Timer Balls (after 40 turns) are the best, statistically.
When it comes to Regigigas, Giratina, and all those other non-travelling legendary Pokémon, just stock up on Dark Balls and Timer Balls, save, battle them at night, use your legendary strategy, and if you run out of PokéBalls, reset and try again.
*EDIT: With a Wobbuffet out