So I did this when I am at 105.
The issue was: At the stone pillar, there are actually 4 orcs (1 on each... side). However when I would stand there only 3 would attack. The backside one would never come. So for 2 hours straight I kept doing this and failed.
Then for the heck of it, I ran around it.. and BINGO, there were multiple orcs stacked up. I killed them and did it one more time (since it was jacked up). The next time she spawned I made sure to kill all 4 each time and it worked.
So it was buggedish, because of my level