Since BC onwards, we've generally gotten help.
Maiev helped us kill Illidan.
We didn't really beat Kil'jaeden so much as stall him until Kalec could snap Anveena out of her trance and she could turn the power of the sunwell against him.
Malygos would have killed us if we hadn't gotten help from the red flight in the last phase.
Yogg Saron, we had the help of the four Keepers.
Lich King actually DID kill us, it was only Tirion pulling a dues ex machina with his final light prayer and shattering Frostmourne that did him in, with the thousands of spirits within leaving him helpless for us to finish off.
We had help with Sinestra if I'm not mistaken, I think Cael did something there anyway.
Ragnaros 2.0, you only kill him in the heroic mode where Malfurion and Friends come in to help you.
Deathwing? All we did was tear off his armor plates and buy time for Thrall to finish him off with the Dragon Soul.
Even the Sha of Fear we're only able to beat because of Lei shi creating that shield from his fear breath.
As for us 'stabbing at their feet' that's just a matter of gameplay/story segregation.