Because I was made aware that the Trainer-Fly glitch has been used, I feel the need to point out information regarding something about encounters in gen 1:
When one encounters a wild Pokemon, the game checks if it came from an encounter table (like tall grass) and if it didn't, it assumes it came from a 'special encounter' so the game will remove a sprite from the removable objects in memory to stop the player from doing the event again.
Because Trainer-Fly doesn't originate from an encounter table, any encounter from it can remove an object for the current area. If the location does not contain any one-time object, it will pull from the last list in memory. (ie: entering Route 12 and performing Trainer-Fly on route 6 and 11 (who lack removable objects) allows the Snorlax on Route 12 to be deleted)
In your specific instance, the most likely cause for Moltres to be gone was that Victory Road 2F was the last map with removable items in memory and the game ran code thinking your encounter was one-time and deleted Moltres.
Source: https://bulbapedia.bulbagarden.net/wiki/Mew_glitch#Snorlax_skip_glitch