Right now once a player has thoroughly explored the map, they have full and instantaneous knowledge when any foreign planet changes sovereigns, when any foreign planet gets a designation change, etc.
To make exploration/reconnaissance significant throughout the game and mass attacks at a distance less trivial to mount and launch, I suggest that only planet locations and planet designations at the time of scouting be "remembered" outside of the active sensor range of player fleets. The area outside of current fleet sensor radii should be depicted differently (e.g. with darker shades). Perhaps the age of this information could also be indicated somehow.
To prevent players from saturating the map with explorers, there should be a high but reasonable cap on individual players' fleet counts, possibly tied to the number of planets the player controls.
In lieu of stationary explorers, there can be other mechanisms for gathering up to date information.
1) It should be possible to build either a resource-consuming building on a planet or an attackable construction in space that serves as some sort of superluminal telescope. Each telescope can be pointed at a maybe 250ly radius region of space to give up-to-date sensor information, but it should have a multihour cooldown after the telescope is reoriented before it can look at a different target; maybe the telescope should have its target visible to other players. Perhaps telescopes can also be ordered to track moving starship-speed fleets. The advantage of a telescope over an explorer fleet would be that it would not be subject to attrition, could not be destroyed by jumpmissiles or attacked inside enemy territory, and would be less revealing of the player's intentions; the disadvantage would be that it would be more expensive to maintain, slower to put on a new target, and could be destroyed in situ. The telescope structure should consume resources (aetherium? aes?) continuously when operational and any interference to the telescope resource supply should cause it to go on a multi-hour restart timer rather than resuming operation immediately (otherwise people will game the system by cutting off supplies when they are AFK).
2). It should be possible for players to propose the establishment of reciprocal embassy structures on one anothers' imperial capitals, providing sensor data for the capital and immediate vicinity. Each player could be limited to say 3 embassies. A foreign embassy on your planet could provide some minor bonus but not enough to make creating a second empire attractive just to be able to trade embassies.
3). Having an embassy with another empire should allow the player to propose an exchange or gift of the most up-to-date map data.
4). You should be able to click on any Mesophon world and buy sensor data from it from around say a 500 LY radius, with the cost of the data varying depending on how many non-independent worlds are in that radius.
This suggestion partially hinges on citadels being able to autofire and/or the implementation of SRMs so that empires can have a way to exclude explorer fleets from regions of space even when inactive. As long as explorers can pass freely at any hour of the day or night other mechanisms for reconaissance will be less attractive, even with fleet caps.
These are all great suggestions Watch TV. Right now I have hundreds of explorer fleets scattered around the galaxy to keep watch on fleet movements, an alternative idea could be allowing players to designate worlds as "listening posts" to serve a scout-tower-like function, revealing all enemy fleets and planet designations within a certain radius.
Another idea: perhaps additional units such as spies or saboteurs could be introduced, and sending them to hostile worlds can decrease production, destroy ships or even incite civil war. Or they could be used to provide updated map info too. Of course, these would need to be balanced somehow (requires a special doctrine - Cloak and Dagger?)
There was an "outpost" construction in old Anacreon that did exactly what your listening post suggestion did.
IIRC spies and saboteurs were a big component of the browser game Imperial Conflict which has some similarities to Anacreon.
Foreign empires' trade routes would also require active exploration and not be updated in fog under this paradigm too. Alternately they could not be mappable by fleets at all, requiring some other intentional nontrivial action on a player's part to map.
This would add a level of strategic depth to attack planning, as players wouldn't always know where the most disruptive targets to strike (beyond the obvious hub-capital-foundation) without additional advance preparation.
Trade routes weren't conventionally visible in Old Anacreon since they were composed of actual moving fleets (which allowed piracy), and they are invisible in New Anacreon if one of the two planets associated with the route hasn't been mapped.
On further thought, a more complete fog of war would also increase players' incentive to create multiple accounts in open games order to get a better tactical picture of the map. Not super desirable, so more peoples' thoughts about this topic would be valued.
In a closed game between known players this wouldn't be an issue.
The focus of the game is wrong then if you want to add fog of war.
Instantaneous information means the marginal cost to additional knowledge is low.
Either add an information delay, or move the focus of the game to some aspect of galactic politics other than totalitarian total war. Certainly CK2 in Space sounds fun.