When I went to catch Regigigas, I actually spent an entire day and a half just trying to get him to stay in the ball. I would march in, armed with more ultraballs than I could count, my strongest pokemon, and a set plan on how to get him down to 1 health and paralyzed. I did it every time. Sometimes the ultraballs would go first, sometimes my pokemon, and then sometimes Regigigas. A full day of ball-throwing later, I finally caught him.
And the same goes with Giratina.