If the AI gets no FOW at higher then normal difficulty, wouldn't a possible fix to simple have some kind of outer limit based on its average ship range, that then perhaps is further reduced by a 30%-40% (testing needed) for the purpose of claiming it. That way even if it sees a relic in the middle of no where due to being omniscient the game will tell the AI, dont get that until it falls within the specified limited range. Note im not saying to physically reduce there ships range, they are allowed to move fully within there range, but just use that figure in order to determine a almost fake distance of what it has 'explored' or seen.
That way with each subsequent ship range upgrade, colonized planet or star base deployment. The AI would more accurately simulate AI scouting at a level and speed the player would be capable of.
Likewise it should also give lesser priority to things deep within other AI/player territories, and also anywhere there is a large area of empty space. As in most cases the AI shouldn't be willing to travel there early on. That is unless it feels that its equal or more powerful then the controllers race. While giving more priority if its near a star, seeing as that's the correct scout behavior if the Ai scouts were actually good.
More so if an AI ship comes within one full move/turn or 'visual' range of a relic or resource it can then flag that item as claimable, superseding the above limiter.
Then hopefully we wont see as often the AI sniping a relic or resource deep in your territory, or clear across the map. This would also help with the AI spreading itself to thin in some places by keeping more of its star bases closer to itself meaning it has a better chance of defending them.
I remember Brad saying something about the reason the AI can see everything is because if they had true FOW like the player they would need to save a value for every hex for every AI telling it if its seen a hex or not. Times that by a 100 Ai map and that's a huge number! But seeing as 99% of the map is empty its kinda over kill to save every hex value. As the limiter/figure based on range idea would in affect reduce the need for saving every value of every hex in its entirety. Although I have no idea if it actually calculating that each turn would be a big strain, I cant imagine it to be seeing as ship ranged, when the AI moves, is already being calculated per turn.