This guy was one of the players back in the Classic format. Most of the big decks were based entirely on PokePowers; think Rain Dance, or Alakazam. He was one of only two guys who could take down the infamous Mr Mime in one shot (the other being Nidoking). He also took care of Ditto, though Ditto only really took the stage toward the later stages of Classic format.
Unfortunately, he suffered from having a bad weakness (Psychic was a powerful colour to be in back then), a poor typing (not much is weak to grass) and only 70hp is kinda iffy for a stage 1. The attack is solid, though nothing to write home about, and two retreat makes him slightly vulnerable. Most of the time, though, he isn't going to be in the active slot, his power works just as well from the bench.
His Basic, Fossil Grimer, was acceptable, and although the Psy-weakness problem exists again, Grimer has a paralysis move for only one energy, making it possible to stall with him. Being a Stage 1 also meant that Muk could not make effective use of Scoop Up.
Overall, useful as an 'answer' to PPower-based strategies in decks that need it, not really a competitive body, but not one that can't get a few solid hits in if it gets Gusted into play. Among grass-type choices, it obviously stands in contention with the legend Scyther, which was clearly the best grass of that era, providing a similar body to Muk, but at Basic, with 0 retreat, and a resistance.
Muk's best use was seen in custom Haymaker builds, which used it as a middle-game drop to shut down Rain Dance decks that it had trouble with. Haymaker, which rarely made use of Pokepowers itself, didn't really suffer from the addition of one small line like that, and it definitely increased the deck's endurance against Rain Dance. Against Mime/Pther Psy builds, the Mukmaker deck was ok, I mean, Muk's power still functioned to shut down Mime, Gengar, and Alakazam's powers, but the fact that Haymaker was ok against Mime anyway, combined with the fact that the others were stage 2's (late game) meant he really did nothing, aside from clogging up the bench with psy-weak Grimers.
Overall, I would rate Muk the 2nd or 3rd best Grass pokemon of that format, behind Scyther and maybe Pinsir.
7/10 for usefulness