Shedinja is pretty hit or miss. Only in the sense it will hit you or you will miss it. On the last team I used, 5/6 pokemon had something to hit Shedinja, and the 6th had toxic (which doesn't count as much because Xatu, I know). Fire blast x2, crunch, air slash, and rock blast (kills through focus sash!). And I didn't even think about Shedinja even once. None of them weak to sucker punch, btw.
Some teams you can wreck, and against other teams, you're going in with 5 pokemon almost.
Not true! At all! Obviously your team is the exception. And frankly nobody is about to counter team you here, if you could just copy and paste your team here I could probably show you why A. Shedinja probably can still trouble your team or at least not be dead weight or B. Why your team is so extraordinarily rare.
Every single team you face is almost surely going to be using at least one of Raikou, Roserade, Milotic, Suicune, Azumarill, Roserade, Registeel, Swampert or Slowbro. All of those Pokemon have virtually no chance of touching Shedinja so you can essentially not care about them and let them set up Subs or boosts and not give a crap because you know Shedinja will come in to force them out later. You sir are the one starting off what is essentially 6-5 or 6-4 or 6-3 or better as long as you can recognize the fact Shedinja needs hazards off the field.
But that list is far shorter than what Shedinja can usually beat. Bisharp is going to have to predict like mad not to waste Sucker Punch. Snorlax has to run Fire Punch or Crunch instead of its usual 5 moves of Curse, Whirlwind, Body Slam, Rest and Sleep Talk. Zapdos must be using Heat Wave or Toxic or its a goner. Nidoking has to be running a Fire coverage move. Bronzong has to be using Toxic. Cobalion must be running Stone Edge.
And Shedinja is still not done raping UU yet! There is a whole other list of Pokemon that seem to check Shedinja but to no avail, the things that fall to priority. Darmantian takes at least 70% from a +2 Sucker Punch. Chandelure is OHKO'd with hazards as is Victini. Mismagius is also maimed while Xatu is badly injured by a +2 Shadow Sneak.
Of course I'm not done yet though because I personally think all posts should be obnoxiously long to get the point across. There is yet another list that Shedinja can take on, the Choice users. Do you consider a Flygon a Shedinja check because it has Stone Edge? Wrong because I bet you you probably could have taken off Stone Edge and just have U-Turn/Outrage/Earthquake and probably not notice you were missing Stone Edge for a few battles. Unless you feel comfortable locking yourself early to midgame in a Flygon's Stone Edge, Shedinja is staying on the field, stealing your momentum away when you try to U-Turn. Choice Scarf Heracross is unable to spam STAB moves if he is Choiced (Orb variants may actually be completely walled!) because the looming threat of Shedinja. A boosted Shadow Sneak can do over 50% so Heracross will spam CC as Shedinja comes in. As Hera switches Shedinja may use SD if team preview permits and proceed to sweep if the opponent has no way to touch you apart from Heracross because the Focus Sash will save you if Heracross is still at +60%. Choice variants of Vicitini and Darmanitan that try to get cute with U-Turn are met with a dead cold and empty husk that halts all momentum. Its pretty simple, make sure you can win (which is obvious with team preview), wait for your opponent to understimate you and make a mistake like using U-Turn midgame. Use SD as they flee your Shedinja and maim anything standing in your way knowing you can survive at least one hit because Focus Sash and knowing priority will likely kill the choiced user when it comes back in to try and revenge you. Also true for Escalvalier but that needs to be weakened a bit if you cannot force it out, although he is one of the Choice pokes you can actually outspeed so two +2 X-Scissors if you have your Focus Sash intact should do some damage I suppose (I never tried it).
There are of course more Pokemon Shedinja can defeat and then win whole games with. If your opponent is in the mind set of "All I need to do is keep my Krookodile alive and then Shedinja ca't beat me" then awaken them rudely. Krook will always fall to Shedinja if Shedinja has a Focus Sash still because it has a Super Effective X-Scissors. This is also true for Zoro and Sharpedo as well as other frail things that crumple under one X-Scissors+Sucker Punch such as Houndoom.
I must have listed over a dozen, maybe two, unique UU pokes, all of which are at least decent in UU and all of which usually/always lose to Shedinja. There are more. The only true negative aspect of Shedinja is that it demands the expensive luxury of no hazards on your side while keeping Stealth Rock on your opponents side (which actually is almost easier said than done with Xatu).
edit: i'm not so sure anyone believes me yet so look here
http://www.smogon.com/forums/forumdisplay.php?f=120&prefixid=rmt_mode_uu
Every single team in the first 15 or so RMTs have at least one Poke that cannot touch Shedinja while practically all their SR users are weak enough to be walled by Xatu. Many teams have two or three.