I'm currently playing my first 0.96 RC10 campaign, I'm playing with a High Tech ship only (minus logistic ships like Salvage Rigs or Tugs) style and without a commission, I've worked towards getting friendly with both Pirates and the Path and once my colony got strong enough to hold its own I've made enemies with Indipendents, Hegemony and the Persean League.
Despite all that, I've essentially managed to find high to very high contacts with most factions (I only picked Pathers and Pirates since they were most useful).
The problem I seem to gather from what you said Amoekba is that finding contacts is not as straightforward as you might think. The absolute best way to find them is to do missions for agents in any and all colonies. I have for example found my Very High Pirate contact in Echou Bres by doing a spysat mission, next thing I knew he offered up to a Million credits worth of "not so legal" nanoforge use, which I used to get an Odissey plus a plethora of Revenants and Phantoms to uh...do buisness with factions I'm not currently friendly with.
By Ludd, I actually got my Very High Luddic Path contact by just casually trading and chatting in the bar of a High Bounty Pather base I originally was going to to get the money, which had me abort the mission and develop the contract instead!
In short, it does not matter what you're doing at a planet, always check the local bars first, you'll never know if you strike gold!