I think you make the calls right outside Lugia's room, but I'm not sure; I've never RNGed Lugia. I've heard you can advance frames by however many pokemon are in your party, every time you walk 128 steps. I'm not sure about that though.
I have never RNGed the roamers, but I probably will on this playthrough of SS. Lugia can be RNGed, but you have to make the Elm calls outside Lugia's waterfall/cave thing because there's no reception inside.
Yes, you have to RNG twice for eggs, but that's only if you want them shiny.
Sorry, I should've told you to look for that. From now on, always look up to 3 letters ahead, just in case.
Here's a list of things that can make it skip letters (frames):
Raikou - if Raikou is roaming around, one letter will be skipped
Entei - same as Raikou
Latios/as - same as above, the roaming one will skip a letter
NPC movement - if an NPC (non-player-controlled) person moves at all, it can advance the frame. This is why you should always get into PokeGear as fast as possible.