I was able to find some explanations in the script, and that's only Gold/Silver/Crystal.
The explanation, overall, seems to be that they were newly discovered:
GOLD! There you are! I needed to ask you a favor. I have an acquaintance called MR.POKEMON. He keeps finding weird things and raving about his discoveries. Anyway, I just got an e-mail from him saying that this time it's real. It is intriguing, but we're busy with our POKEMON research. Could you look into it for us?
I'll give you a POKEMON for a partner. They're all rare POKEMON that we just found. Go on. Pick one!
Yo, GOLD! I hear PROF.ELM discovered some new POKEMON.
PIKACHU is an evolved POKEMON. I was amazed by PROF.ELM's findings. He's so famous for his research on POKEMON evolution.
PROF.ELM claims EEVEE may evolve in new and unknown ways.
I am JASMINE, a GYM LEADER. I use the steel-type. ...Do you know about the steel-type? It a type that was only recently discovered.
I'm waiting to see SLOWPOKE's moment of evolution. Through observation, I made a new discovery. A SLOWPOKE with a KING'S ROCK often gets bitten by a SHELLDER.
Some of the new Pokémon are ancient Pokémon that were only recently rediscovered, like the Unown:
The strange POKEMON you saw in the RUINS? They appear to be very much like the drawings on the walls there. Hmm... That must mean there are many kinds of them...
Porygon2, on the other hand, is artificially made:
This manmade POKEMON evolved from the latest technology. It may have unprogrammed reactions.
Here's some related dialogue about new moves:
TM49 contains FURY CUTTER. If you don't miss, it gets stronger every turn. The longer the battle goes, the better it gets. Isn't that great? I discovered it!
Alternatively, consider Bill's explanation, that these Pokémon (and moves) "didn't exist":
You know that POKEMON can be traded, right? My TIME CAPSULE was developed to enable trades with the past. But you can't send anything that didn't exist in the past. If you did, the PC in the past would have a breakdown. So you have to remove anything that wasn't around in the past. Put simply, no sending new moves or new POKEMON in the TIME CAPSULE.
(I like to think that the PC revolutionized Pokémon trade, which in turn lead people to release new types of Pokémon into the wild. That way, you wouldn't find some species because they're not supported by the PC system. I assume the reason you don't find any unsupported Pokémon is because it is essential for a PC to support the local species.)