I'd like to second that the odds of contacts seems low.
I'm maybe mid-game? March, Cycle 210. 3 colonies (size 4, 3, 3), Paragon, Aurora, Champion, 3x Herons, Hammerhead, Drover, Tempest (and a Legion XIV stashed waiting to be restored). I have 1 contact on my intel contact tab, which I gained after the colonies and Paragon. So besides the Academy contact, that is it. I had been trying to pick up a faction military contact (by doing bounty bar missions), but when the intel tab bounty missions that just show up by flying near a comm relay in hyperspace are more lucrative (250k-300k) it's rough picking up only a 100k bar bounty that goes to the edge of the map. Probably did around 8-10 of those bounty bar missions, every time I found one, before the permanent contact offer. So I've had to go out of my way, in a non-economical sense, trying to get a bounty hunting contact just to see what they do.
In hindsight, I'm realizing the spy satellite, war crime bombing, and marine raid missions are also probably potential military contacts.
On top of potential contacts sticking around, I really would love the ability to spend a story point and say, "I want this good contact with faction X (Tri-tach, Hegemony, etc) who offers missions of type Y (Military, Trade, etc)."
Actually, out of curiosity, does taking a commission get you an automatic military contact? If not, that might an interesting way to have the player express interest in contacts of that faction type. I suppose I should just try it and find out.