When it comes to Ubers, it doesn't matter if a Pokemon is useful or not. If it is too strong for OU, then it gets banned, simple as that. Mence's situation in Gen Four can be summed up as too unpredictable and capable of claiming kills just about every time it comes in. To quote FSG, "Salamence can mix and match whatever moves and stats spread it wanted." Predicting its set isn't as simple either since Mence would claim a kill every time you try to guess what set it's running
Here are a couple videos that goes into full detail on why Mence got banned. In the second video, skip to 4:23 to get to the Gen Four part since it covers everything from Gen Three to Six.