Maybe there could be some kind of fog of war so you can only "know" about places that are somewhat close to you or that you've sent your chancellor to. And you can only marry from the places that you know about.
I'd prefer a scaled fog of war based on relative distance and maybe a few other factors. You should be able to see all of the map, but while a Duke of Iceland might know who the King of Abyssinia and his heir apparent are, he probably doesn't know all of Abyssinia's random courtiers or even the extended royal family. On the other hand a ruler in one realm might know the court of a neighboring realm but not perfectly, so some people would be missing or their stats and traits skewed. This could all be influenced by Intrigue, or maybe by Learning, or a combination of both, as they both influence information and knowledge gathering. Perhaps councilors could even help out with it, in the same way that a councilor in a foreign province lifts the fog of war from that province.
This fog of war should probably also apply to technology and building levels, maybe even supply and geographical information.