Well there is probably always going to be a counter for any deck, so focusing too much on one particular threat can be unproductive, but...
You could easily see her at site 5 with
Steward's Tomb, or any other site five if you put just 1 twilight in before moving. Maybe at site 4 if he uses
So Polite. Frodo with the ring is an effective counter for the most part, but it wouldn't be too suprising to face gollum and shelob at 4, 5, 7, 8, and 9. That's with your Frodo/Sam/Smeagol version of this deck. The other versions with the elves gives more pool and Shelob comes in easier.
They Stole It plus the ring means a minimum of 3 burdens each time you fight gollum (5 if he uses
They Stole It twice in a skirmish). I'm not saying you are doomed or anything, but that shadow combo may be a bit dangerous.
Oh, you won't clog a deck with
They Stole It in it. Even if Gollum can't hurt Smeagol, the shadow player can still use
They Stole It to toss as many cards as are needed to cycle.
Consider this not too unlikely sequence.
Captured by the Ring and
Fat One Wants It have added three threats by site 5. He uses
So Polite to play
Gollum Mad Thing (who is fierce thanks to
Hidden Even From Her) and adds 1 to the pool. There is now 10 to play with. He plays
Her Ladyship Paralyzing Smeagol, and still has 6 cards in hand. You put Smeagol against Frodo and Sam agains Shelob. Sam is going to take two wounds. You add one burden so Gollum will be S5 instead of 8. Frodo puts on the ring (1 more burden). Gollum throws 3 cards (2 more burdens), then does it again (2 more burdens). 6 burdens have been added in just one skirmish phase. You exert Frodo twice to overwealm Gollum with
sting so you don't have to fight him again. In regroup you toss Smeagol to remove three burdens. Next turn you play Smeagol healing both hobbits and adding 1 burden. At the end of this whole process you have 4 more burdens than you started with. Repeat at 7 and 8 and you are corrupted.
(Not sure which deck we are even talking about since you posted 4 that are variations on the same theme. The suggestions were general, not really directed at any deck in particular.)