I did BRD (Blackrock Depths, vanilla dungeon) approximately 200 times on my Rogue (at level 60) to attempt to get the Barman's Shanker. This was when you had to find your own group and usually with how long the instance was they would fall apart before reaching that point because that was about an hour and a half into the instance at that time. It dropped once of those ~200 times and I never did get it until my Rogue was level 68 in BC.
I ran pretty much all the level 66-70 dungeons attempting to get the dungeon set (Assassin's?) in BC at least 30 times each, I ended up getting the items stolen from Druids and stuff so many times I gave up (Rolling is also part of RNG.) I also ran that Black Morass instance probably 75+ times to try to get the trinket. I think it was a couple months before Wrath came out that I got that Trinket on my Rogue, got it second run on my Hunter.
Wrath I didn't play too much but I remember farming the Crusader Tournament dungeon at least 60 times to get all my needed items in that place and all of them have around an 8% drop chance.
Cata did not introduce RNG.