I actually completed this one a day or two again--maybe just by luck. Couldn't find the guy, waited outside the castle for a while then gave up on it. A little later I noticed a group of 12, including one "Ordinary Townsperson," standing by the forest on the Swadian/Rhodok border (pretty far away). The group was kind of a neon purple color and was just standing there waiting.
When I bumped into them my greeting was "You are under arrest by orders of King Ragnar!" I attacked, chopped down the guards but made sure to use a mace to knock the townsperson guy out (instead of killing him). So that worked. Then, when I exited the battle I had automatically found the spy too. Took him down in a one-on-one with a mace too, and had them both captured. Ragnar loved me--finally some validation in life! Just kidding...hope this helps.