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.