The Envoy's primary quest was to determine which ruler controls which Yorovashian castle. In his travels across the land's twenty regions, he picked up twenty clues. Together with the map pieces granted from answering the puzzle, these clues can be simplified to logical statements that help us determine the locations of the twenty rulers.
However, it is evident from just a few pairs of clues that not all of them can be true. Clue 4.4, for example, says that the longest-named ruler owns the longest-named castle, implying that Lord Magreillium rules Castle Mornstallinar - but this conflicts with Clue 5.4, which says that Lord Cillarie rules Castle Mornstallinar.
Savvy solvers might guess at this point that there are systematic lies spread across the stories - perhaps one lie per Act, or even one Act that is entirely lies. These assumptions aren't necessary to solve the puzzle. We will aim for the solution with the least amount of lies using the clues and map alone.
Some of these clues (2.4, 4.1, 5.1, 5.3) are more powerful than the rest. If we're lucky, all of these clues are true. The story's tone might also suggest that certain characters are a little more trustworthy than others, but we'll just try working through the clues in chronological order and deal with contradictions when they arise.
1.1 Lady Lorwen rules Nightail. Let's mark this down.
1.2 Lord Sordras rules Hulnarth and Lady Azurem rules Quellsire. Let's mark these down.
1.3 Angroth and Azurem are not adjacent. This currently implies that Angroth does not rule Durmstrog or Sildrim.
1.4 Lord Sordras rules Hulnarth. We already have this.
2.1 Lord Magreillium and Lord Peritto rule regions on the east and west coasts. There are about four regions on each side of Yorovash that fit this description.
2.2 Lord Faeletti rules Morimoor. We'll mark that down.
2.3 Lady Violath rules Erennor, and Lady Yrn and Lady Tern rule Zu and Stormtithe (though we don't know which). Marked.
2.4 No House starts with the same letter as its ruler. This holds up so far, so we'll assume it's true.
3.1 Lord Rylus rules Rattlefax. Here's our first conflict: 2.4 says this can't be true. We'll mark this as a lie for now.
3.2 Lord Numinort rules Skrar. Marked.
3.3 Lords Angroth and Cillarie are adjacent. This doesn't help much yet.
3.4 Ladise Eorith and Jacquelis are each adjacent to only one other lady. Noted.
4.1 No two adjacent rulers have the same last letter. This holds up so far.
4.2 Lord Fabrax and Lady Gyrook are adjacent. Noted.
4.3 Lady Zorra rules Velverst, and Lord Numinort and Lady Yrn rule Pallow and Zu (though we don't know which). Here's our second conflict, as we've already marked Numinort in Skrar. Let's side with the more complex clue in this case, and remove Numinort from Skrar. 2.3 then implies that Yrn rules Zu, Numinort rules Pallow, and Tern rules Stormtithe.
4.4 Lord Magreillium rules Mornstallinar and Lady Yrn rules Zu. The first part of this conflicts with 2.4, and is the second clue to do so after 3.1. Since Magreillium ruling Mornstallinar meshes with 2.1, and we already have Yrn marked in Zu, let's go back and mark 2.4 as a lie, reinstating Rylus in Rattlefax as well.
5.1 Rylus, Faeletti, Fabrax, Silvia, Lorwen, and Zorra are all landlocked. We've already marked Rylus, Faeletti, Lorwen, and Zorra in landlocked territories, so this clue is looking good, but it's still possible that the clue was only partially true. For now, we'll note that Lady Silvia and Lord Fabrax probably rule Ankhrete and Skrar.
5.2 Holayn rules Kreykaarth and Ladies Jacquelis and Gyrook rule Ornst and Faz-Lygor. We haven't placed any of these rulers yet, so we'll mark this down. Using 3.4, we can pin Jacquelis to Ornst, as otherwise she would be adjacent to both Gyrook and Zorra. This makes 4.2 a probable lie, as there's no way Lord Fabrax can be next to Faz-Lygor if his region is landlocked. It also lets us use 2.1 to place Peritto at Sildrim, the only remaining west-facing coastal region.
5.3 No ruler is adjacent to more than two rulers of the same sex. This powerful clue matches everything we have so far, and should let us place the remaining rulers momentarily.
5.4 Lord Cillarie rules Mornstallinar. This would cause all kinds of upsets to our solution so far if it were true, but let's look at the lies we've marked so far: 2.4, 3.2, and 4.2. It's looking very likely that there's one lie per act. Let's mark this one as our lie for Act 5. Our lie for Act 1 is then almost certainly 1.3 - and if Angroth and Azurem ARE adjacent, we can place Angroth in Durmstrog. All that remains is to assign Silvia, Eorith, and Cillarie to Ankhrete, Lyre, and Myon. 3.3 tells us that Cillarie must be adjacent to Angroth in Lyre. 3.4 tells us that Eorith must be in Myon (else she would be adjacent to two ladies, Silvia and Lorwen). This finally means that Silvia must be in Ankhrete - which we also had from 5.1.
We have a solution and have identified exactly one lie per act. What's next? We haven't used the names of our informants yet. Now that we know whose clues were false, we can take them out of consideration.
Solena, Tomas, Ilvos, Natron, and Gem are the liars' names in act order, and their initials spell STING. This must be the name of the deceitful force working against the Envoy.
With these letters removed, the fifteen remaining informants' initials (barring the unnamed innkeeper in Faz-Lygor) give us the message JOINRUL_RNAMEAZ. The missing letter must be an E (who could that be?), and this message tells us to connect the ruler names on the map from A to Z. Starting with Angroth in Durmstrog, we connect to Azurem in Quellsire, and so on until we reach Zorra in Velverst.
The symbol revealed is that of an ANCHOR, which must be the key word used by whoever encrypted the hidden note.