I look at the time travel "problem" this way:
Time's arrow points one way. Assuming time travel machines are built, they allow a certain amount of exploration, but they don't always permit wholesale revision of history. Time can be considered a form of energy, or at least represents the flow of energy in the universe. An expression of entropy, if you like, though that definition is not fixed. Energy, like water, tends to take the path of least resistance.
When the Godzillasaurus was removed from Lagos Island, it was done so by people who already knew it would become Godzilla, because that had already happened.
The creature was removed, dropped into the ocean, and was irradiated there. Even if the rest of the world had "lost" Godzilla, the people responsible for the alteration would still know, so assuming he'd vanish from history was a basic and total error on their part.
Godzilla was originally created, lived for a number of years, and would eventually die during the Destroyah incident. Being moved retroactively did not erase Godzilla but instead gave him a net power boost. This boost allowed him to triumph in his later fights and was at least partially responsible for his eventual meltdown. Godzilla in his original form vanished and reappeared in the same effective instant in larger form. Everybody remembered him because there was no interruption of his overall existence; even the Futurian leaders admitted as much when presented with the evidence.
Since Godzillasaurus was seriously wounded at the time of his move, there is no problem with his perceptions creating timeline problems.
King Ghidorah didn't appear until as late as he did because the Futurians planned for his appearance then, not earlier. The whole point of their operation was to punish the Japan of that particular time, after all.