I've traveled to a coven that way. You need extraordinary luck to find a map to those places
Not really. I actually played one game in which I found maps to 13 of the 14 covens. (Admittedly though, it was a loooong game).
The thing to remember is that any map you find is always (except in very rare instances) to a dungeon NOT already on your game map.
Thus, if you are in a kingdom (which has a coven) that doesn't have very many dungeons, your chances of finding a map to a coven aren't all that bad. And with each "new" dungeon you find, the chances of finding a coven map increases.
One way to find "new" dungeons is to accept a quest to that dungeon.
Obviously another way is to find a map (most likely as random loot).
Because dungeons have the most random loot, the best way to find a coven map is to start dungeon crawling in a kingdom with only a few dungeons. (I have found as many as 7 maps in one dungeon, but the average is probably closer to 1 - 1.5 maps per dungeon).