Does a Pokémon Crystal game degrade after playing a lot?

As strange as it sounds, you are not the first to encounter this. Someone else posted on this forum pretty much exactly the same thing as you - a Feraligatr in Gen II that has problems being hit with paralysis.

In any case though, I have a very good feeling this is not due to degredation. Something in the back of my mind is tickling that the phrase "it doesn't effect" implies that a move that does no damage but gives a status effect has missed, whereas "it didn't effect" implies that the target is immune to the move. I'm guessing that's the best answer here, but I thought they fixed the "100%-accuracy moves are actually only 99.6% accurate" problem in Gen II.

Either way, this is a minor problem that I do not believe is indicative of any technical issues.

The only things that usually "degrade" in a gameboy cartridge during a normal lifetime are the battery and the electrical contacts. The battery will eventually die causing a loss of all save data and the ability to save (the battery is apparently replaceable). The contacts can also corrode, which can make the game temporarily unplayable.

Nothing happens to the Random Number Generator, which is what you're describing here. Crystal, like almost all videogames, uses a pseudograndom number generator, and sometimes quirks in how numbers are generated appear; this can have effects like certain moves are more likely to take effect on certain turns in the battle due to certain predetermined sequences of numbers. If you're seeing anything at all, odds are it's a quirk of the PRNG.

Sometimes games have long, preset strings of pseudorandom numbers that are generated at certain times like when the machine is turned on; in many early games (like the Pokemon Trading Card game) this is noticable if you savestate and repeat an action; "random" actions like coin flips will always occur in the same sequence if you restart from the same savestate.