As it happened, my Octillery is a FRLG one, but you can catch Remoraid in the Emerald Safari Zone once you beat the Elite 4 and they open the expansion area.

In regard to the catch rate of Lugia... according to the formula at Bulbapedia, it's:

floor(((Total HP *4) - (Current HP * 2)) * Catch Rate / Total HP) + Status Mod +1

Catch rate for Lugia is 3, status mod is 10 if asleep, 5 if paralyzed, poisoned or burned, 0 otherwise. Ultra Balls double the catch rate. The resultant number is the chance out of 255 of a catch.

A wild L70 Lugia is going to have about 238 HP, so if it was reduced to 1 HP, its base catch rate with Ultra Balls would be 24/255, or 9.41%. If it's paralyzed this rises to 13.33%, if asleep to 17.25%