The Imp Lord pays gold for removal of his enemies, the pixies.

25 Gold for Warrior Pixie

70 Gold for Pixie Queen

The Pixie Queen pays gold for removal of her enemies, the imps.

25 Gold for Warrior Imps

70 Gold for Imp Lord

Though the back story can only be pieced together by adventurers, it seems that the feud began with the Pixie Queen rejecting the advances of the Lord of the Imps as his dialouge seems to imply this is why he wishes her and her Pixies slain. In all probability he began the trouble after being rejected by attacking the pixies, later using Adventurers of Sapience to do his dirty work for him, while the Queen uses them to defend her followers.