In my world, there's an individual (let's call him 'Imm') who takes it upon himself to guide all societies in the direction he thinks is best. To protect himself from repercussions (as well as everyone realizing he's immortal), he uses magic to alter reality in a limited fashion: after he speaks to someone, their brain (and anyone who saw them together) reconfigures to make them think any ideas he gave them are their own and he never existed in the first place, and anything written down (or otherwise recorded) about him becomes illegible or otherwise changes to make it appear he doesn't exist. This magic "kicks in" automatically when he's done his part and doesn't require him to be aware of a memory or recording for it to be altered.
I can think of a number of solutions for identifying Imm, but these all rely on the belief/knowledge that Imm exists. Employing magic to check for altered memories is possible but, again, relies on the belief/knowledge that memories are being altered. Magic in this world is on the wane, so it isn't the first thought for most people.
If it's possible, how could an organization in a Medieval setting uncover Imm's presence in the world in order to retaliate against him or undermine his efforts?