Justice medals do come fairly easy as long as you kept attacking. I play on server 20 and I attacked a Level 10 NPC 10 time each attack hitting 2 minutes after the other and I only got 2 justice medals in the time but I found that the more I lowered the loyalty the more medals I got. I took the Level 10 and all toghter I got 7 justice and 4 nation medals from it.