The Meet the Spy quest is a bit bugged, unless I'm mistaken. In previous versions, the lord would tell you that the spy is wearing a particular item, such as a Straw Hat, but usually something that half the town wore anyway; which made it somewhat easier to identify who the spy was. Now it's just a guessing game, and it can be frustrating to find everyone in the city.
This quest is pretty annoying. Just have to get the right greeting from the quest giver, sneak (or fight) into town, and say the phrase to every normal townsperson you run into. This of course means you have to sneak in during normal business hours. It's only worthwhile because of the decent relationship bonus you get for completing it.