Newcomer here, trying to go along with the Vaulters. 

In the main quest trying to obtain winter shelters, something like  "Our search parties have drawn the attention of roving armies. They are unlikely to leave us in peace, so it will be war..." came up. 

Well I never ever found them...

I understand that some spawn points must be unknown to spice up the game , but loosing the opportunity to win by finishing the main quest is somewhat unfair !

1) For the main quest line, could you change the color of the 'yellow shield' icon (quest mob) to some other color (red?) so at least we known those are the right mobs to kill. 

2) At least tell us where they are with a quest marker, if you are being warned of those "roving armies", someone must have seen them right ? Alternatively spawn them in a region (not at the other side of the map or area controlled by other player...please) and make them stay in that region.

3) Or just spawn them near one of our city and siege it. Do they actually want war or just a game of hide and seek ? 

I don't have the save anymore, I lost for other reasons (penalty for overexpanding can be fairly brutal....) but is was a good 100 turns after spawning those "roving armies..." 

PS : do the other player see the quest mobs with a  "yellow shield" even if they are not part of their respective quest ?  Would any random event killing this mob finish the quest  ?

Thank you for your help !

Quest armies normally move towards you on their own, regardless of where they spawn. If I'm not mistaken, it's also often mentioned which region they spawned in. Hope this helps.