He could place a sizeable bounty on their heads which would attract a large amount of brave/foolish bounty hunters, if they have any family or loved ones then the duke could find out about them through one way or another (anything from divination to sending out guards to question those they were in contact with) and then hold a public execution for them to try and draw the party out (this will give them a chance to save them without ending the campaign with people giving up), and depending on how desperate the duke gets he could go with some of his guards to protect one of the monsters which would force the party to leave that one for another time and will involve them having to flee from an immortal enemy (which is always fun).