Completed this quest last night on the new Combine server. It is obvious to me that in order to make the Orc Lumberjacks spawn you need to be killing as much as you can in zone. On my old server where I was the only one in zone, the Orc Lumberjacks were VERY rare, but on the new Combine server where there were anywhere from 120-190 halflings running around killing things, an Orc Lumberjack was spawning roughly every 12min or so, sometimes 2 at the same time. Still took me about 4 hours to collect the 2 axes and machettes, due to competeing to get to the mobs first! And also, sadly seeing the Orc Lumberjacks being taken to the guards because they were kicking some little halflings butt!
Oh and with regards to my last post, the Orc Lumberjacks don't 'spawn' at the orc camp, they roam around the west side of the wall.
I HIGHLY recommend this quest, the faction is awesome, xp is awesome and the item is UNREAL particularly for a new server. If it wasn't a lore item, I would DEFINTELY do the quest again!