Just a thought but do you and your companions have high survival points or wearing stuff that raises it? I think that will aftect how many random encounters you have.
I thought that only affects how likely you are to finding useful
I thought enemy encounters occurred regardless - survival just affects chance to escape, while speech affects chance to "talk your way out of it" (the latter only available for human enemies, obviously.
Survival also affects chances of finding animal trails, and chances of successfully following those trails.
At least, this was how it was prior to the update, IIRC.