Perhaps all Nincada are infected with the shroom. But if they can evolve before the shroom takes over their body and makes them a Paras then the Shrooms take over their old Exoskeleton....Or something? Then they fly around and enjoy being invincible and guard a Nincada who hasn't turned into a Paras yet to make sure no trainer will evolve it before it's time. Pretending to be it's friend...then moving along once it's too late...searching for the next victim of the shrooms.
So it's kinda like a pretend guardian angel gig. To make sure nothing like this happens to any other shrooms.
(Interesting side note, the only reason I know this stuff on cicadas and fungus that harasses them is because I am an entomologist in training. And I had a big period where I was obsessed with Cicadas.)