I've often found that Great Balls are more reliable than Ultra Balls, especially when it comes to catching legendaries. Ultra Balls are more useful for catching non-legendaries that are high level, though.
If you know what you are going up against (for example Regice), use a Pokemon you know is resistant to it's moves (vs Regice, Skarmory can make all of it's attacks neutral, with high Defence to counter Superpower). Use this to tank while you get something with sleep ability, switch it in and out alternately healing. Thunder Wave also helps, but sleep is more reliable. Overlevelling a Breloom with Spore is your best way, since that has the fastest Spore in the game.