Actually RS can trade with FRLG from the very beginning on (just need the Pokedex from Birch, the Pokenav isn't necessary), but there you need to have completed the Sevii Islands quests to activate the machine.
About Emerald... I just know you have to get the National Dex to get non-Hoenn Pokemon. I never even tried to get it, and the aforementioned Hoenn Dex completition looks extremely difficult to me...
But with a new game in RS and a game in FRLG where the machine has been activated, it will work, i've done that many times by myself.
What does not work is trading a Kanto Pokemon to RS and then to E, or a Hoenn Pokemon to a Kanto version where trading with Hoenn is enabled and then to a new Kanto game.