Fog of war, deception, misinformation, really anything that forces player to engage in information warfare.
Currently, it's as if every fleet is constantly broadcasting its location and status through unbelievably strong comms channel.
I am aware that devs don't consider the game at current state as not even ready for Steam Greenlight, and also that traditional viewrange based fog of war style idea has been mentioned before, so I'll throw some other ideas here for discussion and not complaint of any sort.
1. Sensor strength / stealth rating.
Could be based on ship hull bonus/hull mod/captain perk/terrain (i.e. asteroid belt).
A fleet might disappear (i.e. ambush) or not disappear but display some ships as unknown.
If deemed not overly complex for the game design, maybe sometimes give false information.
Doesn't have to be gradual. Simplified version could work.
This would allow for more diverse hostile fleet composition and strategy at defeating them. For example, say a player is tasked to remove a hostile commerce raiding fleet (could be either pirate or warring faction). Unless player is willing to field a sophisticated sensor ship, which might be prohibitive due to cost/burn speed/etc., the target fleet will hide and not engage player's superior fleet. Player must find a right mix or bait ship/npc bait fleet that would convince the target to engage.
One added benefit to this is that high-bounty pirates don't necessarily have to have a veritable frontline combat fleet with beefy capitals and subcap supports and be very pirate-y.
Also, hidden pirate bases may finally become truly hidden.
2. Feigned faction allegiance
I liked how smugglers switch their flag between pirate and independent.
Maybe it can be expanded further. I'm mainly thinking of Q-ship variants of civilian hulls. Must prey on traders where guards cannot hear, suspicion meter increases based on various actions, susceptible to cargo checks and must roll dice for cover blown check, etc.
3. Give players ability to scan fleets
Opposite to limited information; an opportunity for more information than currently available. For example, player is tasked to defeat a very strong target fleet. Player approaches the target with covert ops variant ships to confirm target fleet's correct composition and equipment/supply status. Player tailors his fleet to counter the target.
4. Advanced AI smugglers
Combination of all three above. Make smugglers fast, agile and stealthy, and maybe use travel routes different from main shipping lanes, making them hard to catch during transit. Even if player does catch one during transit, if the smuggler feigns faction allegiance, player may risk damaging faction relations if player kills the smuggler without blowing his cover first.
Upon arriving at the destination, unloading goods must be near instant to discourage planet camping.
In return, they should give as loot very profitable goods, something related to ongoing shortage or illegal goods highly valued in black market.
5. NPC info merchant
Just throwing it out here