Sounds too far-fetched to think such kind of records are perfectly accurate, and completely safe from fraud, or omission, for example, specially in a world where Information Technology means nothing. Unless we assume a 100% foolproof register system for that type of information, something that is outrighteously absurd.
Remember there is something called reputation as well, and rumors can be, although less reliable, much more fast, cheap and less bureaucratic than checking on a bunch of paperwork to verify somebody's loyalties and past. I have to say that the best solution lies in something that is believable and truly possible. And I'm full of government here and there as well, in the best RPGs I saw, either government participation is minimal and it is based on a big adventure, or government is just something truly evil to be taken down, destroyed, or something relatively good on the blink of destruction to be saved. I say let's go lasseiz-faire for Yliakum, and from the way things are going, it sounds much more believable and I asure you, it will be much more interesting for many people.
Registers are not completely safe from fraud, tax evasion is not something uncommon in any realistic environment, and corruption is not simply a legend. A way NPCs gradually have rumors about Player Characters("What do you know about *PlayerCharacterX*?") as they become more famous or infamous sounds more believable.