If you eventually catch them... is it really wasting balls?
My suggestion: put them to sleep as soon as possible. Don't let them Curse. When they Curse, their Defense goes up, and the higher the defense (combined with the fact that they're Legendaries and, more or less, Tanks) the more difficult it is to catch them (far as I know – I could have been given false information!). So putting to sleep is top priority - do it before even thinking about inflicting a wound. You could also use a Poke with Screech, or a similar defense-lowering move (a Hazer would work wonders if they are able to Curse up). But regardless: sleep first, attack second, and then Haze or lower defense if they've Cursed. And just keep plowing by with Ultra Balls (or Timer Balls, although I personally found them unreliable).
If you have the time, you could configure the ultimate Pokemon Catching Machine: a Shroomish (don't let him evolve!) with Spore (the only 100% accuracy sleep move) and False Swipe.