Scragnoth, way back in Tempest, was the original "can't be countered" creature. On top of its uncounterability and large size, it has protection from blue -- so blue has trouble bouncing or blocking Scraggy after it waltzes through walls of counterspells. But Scragnoth was hardly a blip on blue's powerful radar, until more recent times.... No uncounterable creatures (or other spells) were printed again until Invasion.
Invasion's Blurred Mongoose originally had protection from blue as well as uncounterability, but this was seen as too obviously blue-hosing and was actually changed to protection from artifacts for a while (at which point it would have been an uncounterable version of Mirrodin's Tel-Jilad Chosen)! Eventually it became untargetable instead of having a protection ability: it still hoses blue's targeted bounce spells (like Repulse) but can at least be blocked by the odd Horned Turtle.
Invasion also brought Kavu Chameleon, who adds a beefy 4/4 frame and an Invasion-block-friendly color-changing ability to the uncounterable lineup.
Planeshift's (and now Eighth Edition's) Gaea's Herald continued the charge of bringing uncounterability to creatures, though it is not uncounterable itself. It originally cost a mere (!) but R&D worried that that hosed blue's counterspell ability too much, and its cost was increased to .
Uncounterable creatures reared their head again in Legions. One was Root Sliver -- whose art was originally commissioned for a sliver that donated an ability to block flyers -- brought uncounterability to sliverkind. The other, Vexing Beetle, began life as a pricey 6/6 in design, shrank to a cheap 2/2, and inflated again to its present form: an uncounterable 3/3 with another control-deck-hosing growing ability.
No doubt Magic will see more uncounterable creatures in the future, and blue will continue take it on the chin. But as Magic's pendulum swings, will blue have the Last Word?