I can't find any earlier pictures of Mew despite it supposedly being officially revealed in the May 1996 issue of CoroCoro, but these are from 1997, and they say 幻のポケモン (Maboroshi no Pokémon; Illusive Pokémon AKA Mythical Pokémon) for Mew. 幻 (Maboroshi) simply means something so rare it might not be real, like an illusion. I doubt that the term had real significance back then, but it came to be adopted for later games for the subset of Pokémon that we call "Mythical".
The second Pokémon movie's Japanese subtitle is 幻のポケモン ルギア爆誕 (Maboroshi no Pokémon Lugia Bakutan; The Illusive Pokémon - Lugia: Explosive Birth). Yet it can be caught through normal gameplay in Gold, Silver, and Crystal, which is the opposite of Mew, so it's likely that it wasn't a defined category by that point. The earliest I can find official info for Celebi is Space World 2000 where it was distributed.
https://www.nintendo.co.jp/event/sw2000/sokuho/26/page06.html>ゲームの中では絶対にゲットできない、前作で言うミュウのような幻のポケモンなんですね。>It absolutely cannot be caught in-game, and in that regard it can be said it is most assuredly an illusive Pokémon similar to how Mew was in previous entries.That's probably the point where it became a completely defined term in Japanese.
Ruby and Sapphire continued the trend with Jirachi and Deoxys, but Lugia and Ho-Oh may have obtained Mythical status since they were no longer required to complete the National Pokédex in any game up through Platinum. They could only be obtained through Colosseum (Ho-Oh), XD (Lugia), or through the Aurora Ticket in-game event from FRLG/Emerald where you go to Navel Rock. It wasn't until HGSS that they seemed to lose Mythical status.
Deoxys is obtainable through regular gameplay in ORAS, so its status as Mythical from that point on can be disputed. Unfortunately there's no National Pokédex in Sun and Moon to use as evidence.
