*might get the answer to this*
I've been determined to catch every Pokemon possible in an area, wherever I go (evolutions included)-- Shall I give y'all a number when I meet up with my rival in Cerulean City?
HUGE EDIT, WITH A BIGGER ONE AT THE BOTTOM:
So I did the research and...
Game: Leaf Green
I can aqquire 40* Pokemon if I am adamnant about evolution AND if I have enough Moonstones (three Pokemon need Moonstones, one needs Thunderstone).
*Assuming there was no trading, surfing, or rod-usage and that the rival never bought Magikarp on Route 3, and that he was willing to level up all those caught Pokemon to their evolved forms. Also assuming that he travelled Routes 1-25, took the detour at Route 22 (as one can battle him there after the Boulder Badge is obtained). ALSO there is a mild descrepancy thanks to the difference in available Pokemon between Leaf Green and Fire Red.
Dialogue: "Hey, guess what? I went to Bill's and got him to show me his rare Pokemon. That added a lot of pages to my Pokedex! After all, Bill's world famous as a Pokemaniac. He invented the Pokemon Storage System on PC, too. Since you're using his system, you should go thank him. Well, I better get rolling! Smell ya later!"
There is no actual mention, before or after, about how many Pokemon are caught-- at least, not at Nugget Bridge. On the other hand, if the rival was adamant about evolution, bought Magikarp, and was shown an unknown number of new entries thanks to Bill, there is a chance that maybe he's gained 40+ Pokemon by this point.
In conclusion, it is PLAUSABLE that the rival can indeed acquire 40+ Pokemon (or at least gain Pokedex entries about them), so long as he puts in the time and effort to evolve all those Pokemon to further forms. At this point in the game, catching 40 unique Pokemon is not possible, but evolution+Bill's entries can bring up the number considerably.
Pokemon List for LG and Reference, not including Bill's entries:
Bulbasaur (Rival's pick)
Ivysaur
Caterpie
Metapod
Butterfree
Weedle
Kakuna
Beedrill
Pidgey
Pidgeotto
Rattata
Raticate
Spearow
Fearow
Arbok
Pikachu
Raichu*
Sandshrew
Sandslash
Nidoran(F)
Nidorina
Nidoqueen*
Nidoran(M)
Nidorino
Nidoking*
Clefairy
Clefable*
Jigglypuff
Wigglytuff
Zubat
Crobat
Paras
Parasect
Mankey
Primeape
Abra
Kadabra*
Bellsprout
Geodude
Graveller
Diglette
Dugtrio
Drowzee
Magikarp
Meowth
**Magikarp
**Gyarados
*Possible evolutions not shown in the rival's team to be had yet or needing an evolution stone to obtain
**I didn't buy Magikarp, but it IS possible to obtain if you give up that 500 Pokedollars. Also keep in mind that Magikarp and Gyarados bring our total up to 47.
HUGE EDIT IS HUGE:
AH-HA! The "I've caught 40 kinds!" actually occures on the SS Anne, when you face your rival before earning Cut from the captain. In that case, yes, with the above post still in tact and additional Pokemon caught in routes 5 and 11 (and diglette cave, AND the old rod now used), it is very much possible to get 40+!
... Am I officially a nerd for figuring all of this out? >: