Ok this may be way out of the way for people because of the new wotlk content but I found a way to complete the Make them Pay! pvp quest from Icecrown without having to find people to kill. First off you must have the Make Them Pay! daily quest then travel to Silithus.
I was just doing some old quests there that I had missed to complete the Loremaster achievement in Kalimdor when I came across this trick. In the zone are Silithyst Geysers that you can click on and you will gain movement debuff until you reach the transporter in your respective base camp (I'm doing this on the horde side and assume it works for Alliance). Once you reach the transporter you it will count as a kill for the Make Them Pay! quest. As a bonus, you also get +20 rep with Cenarion Circle and +20 honor for the delivery. Do this 15 times and your are done. Turn the daily in and gain more honor from the quest itself.