In Generation I (Pokemon Red/Blue/Yellow), stats are determined by DVs (Diversification Values) which to my knowledge are similar to IVs in later generations, but only go from 1 to 15, with the HP DV determined by the rest of the DVs. What are the exact odds of finding a Pokemon with all of its DVs at the highest value possible? How hard would it be?
In generation 1 and 2 the IVs went from 0 to 15 for each stat. And there were only 5 stats - Special was one stat, and would not be separated into Special Attack and Special Defence until Gen3.
However, the IV for HP was determined a little differently:
The HP IV is calculated by taking the least significant bit (the final binary digit) of the Attack, Defense, Speed, and Special IVs, then creating a binary string by placing them in that order. As such, a Pokémon with an odd-number Attack IV has 8 added to its HP IV, an odd-number Defense IV has 4 added, an odd-number Speed IV has 2 added, and an odd-number Special IV has 1 added.
Effectively, as long as Att/Def/Speed/Special were all odd numbered, the HP IV was 15 (max). So only four IVs stats were randomly determined.
The chance of getting a single max-IV stat is 1 in 16. The chance for two perfects IVs is 1 in 256. Three is 1 in 4,096. All four is 1 in 65,536. And if all four stats are at 15, the HP is automatically 15.
So the answer is 1 in 65,536 or if you prefer percentages; roughly 0.001526% of Pokemon caught in generation 1 will have perfect IVs
Also keep in mind that in addition to those odds, the earlier generations did not have an NPC to check if IVs were maxed, so unless you're running the game on an emulator that will let you see the stats, you'll need to calculate them with the help of a IV/DV calculator.