Those pokemon with the PID reroll are marked as illegal because they ARE illegal. Is not a bug to report an illegal pokemon as illegal, bugs are legal pokemon marked as illegal and illegal pokemon marked as legal.
Just because older release did not check this legal cases that not means those pokemon are legal, this pokemon always were illegal but now PKHeX have been updated to detect those cases.
The check is not the same in gen 3, 4 and 5 pokemon because the PID and IV is generated with different methods depending on the origin game or type of encounter, in facti in most of the gen 5 cases all PID-IV relations are possible, because the RNG was better than older games, that is way gen5 are not illegal after reroll. The same happens with gen 3 and 4 pokemon hatched from eggs, probably a PID reroll wont make them illegal because eggs can have almost any PID-IV value if they were day care eggs.
It could be helpfull to have a PID generator in PKHex like Pokegen, but there is none yet and those programs have working generators that can be used, that is why PID generator have not a mojor priority. Keep in mind even with that it would not be possible to make a PID reroll like the current button that instantanly gives a valid PID for any values, in most PID generation methods not every values are possible, and even that to find one in particular would require a brute force algorithm that could take minutes or more.
From now if you just want to make a gen3/4 into shiny you can try to reroll the SID instead of the PID, in recent commits a feature was added to make the pokemon shiny chaning the SID instead of the PID, and that would allow a shiny reroll for most encounters without making the pokemon illegal. To use that you only need to control-click the shiny button.