In the Middle Ages, and even up to the early twentieth century, most of Europe's executioners were related: the Sansons and Deiblers in France, the Pierrepoints in England, etc. The reason for this was that, it generally not being socially acceptable to, well, kill people, executioners and their children could, generally, only marry other executioners or their children.
The parallels with massively inbred, Hapsburg-style dynasties are obvious- imagine a rather clever but politically inept satirist noting this, and being sentenced by the latter to a meeting with the former; even worse, imagine a dynasty of deranged and deformed executioners- think Texas Chaisaw Massacre with government funding.
King dresses as a commoner occasionaly and makes his way through the town. It is an unknown occurance so nobody expects it. This time he is mistaken for a thief and jailed. Not wanted to reveal himself, and always curious for the experience, he allows himself to be arrested. PCs also get arrested for something, probably guilty but pay a fine. How they act towards the 'king' could greatly change how their first meeting will be as the players always meet the king at some point.