I would argue that it is a relatively simple solution, albiet one that would require tweaking to have optimal values for the variables in question. I'm aware I don't have access to the AI code, of course, so it could be more complicated than I'm guessing, but it seems like a fairly trivial kind of check.
Loop through all foreign vessels in your space, look to see what planets and resources they are within a single turn of, and base some kind of suspicion modifier off that. When the AI sees enough camped out ships and transports, there is a rapid decline in relations and possibly a diplomatic message. If the suspicion of an attack is high enough, they could even declare war outright without having to go through the decline in relations.
As for the AI moving ships on a per turn basis instead of setting waypoints... yeah, that might be more involved, but that should probably be fixed anyways, if the AIs are to become better able to tactically go toe to toe with the player.
Also, shadowing enemy fleets is tough to do, but I was under the impression that they already did this with transports, so it could be extended to include combat fleets as well.
As already noted, the AI already does this, and as already noted, having the AI shadow the player's fleets, while sounding nice in theory, is complicated in practice. A simple rules change, with a negative diplomatic modifier from the actual use of a surprise attack, is much more simple and doesn't open the way for further exploits.
It would be a simple solution, but it wouldn't cover enough cases or be a strong enough deterent. For example, the situation where the AI DOES attack in self defense (and they will do it, if you hang out transports in orbit long enough), having a diplomatic penalty is not ideal. Also, I'm not convinced it'd be enough... after all, the player is usually much, much more powerful after a successful war of conquest. Besides, thats not terribly believable, either... the most I'd think that a civilisation should do is react on more of a hair trigger to civs that employ surprise attacks.
And, like I said, I was under the impression that the AI would already shadow transports to some extent. If that's the case, extending it to attack fleets as well shouldn't be a huge difficulty.
The AIs desperately need to handle themselves better in the act of declaring and preparing for war. They are neglecting to prepare adequately before making a war declaration, denying themselves the advantages of a sneak attack, and often failing to make a crucial preemptive strike. When they do decide to shoot before they get shot, this can be exploited ass described by Wyndstar. The reason it's so easily exploited is because they recogninze the threat and declare war to counter... but without first moving ships into position or even attack on the turn they declare war, giving the player free reign to wipe them out before they will respond. Moving fleets into one turn striking distance of aggressors before declaring war and allowing attacks on the first turn would themselves go a long way towards remedying this, and a slightly more complex (I'm guessing, since the AI only figures transports into it) model for determining the risk of a catastrophic surprise attack would improve things as well.
Regardless, don't talk about an AI implementation being "too hard" to be done. Without access to the code, you can't make that judgement any more than someone can say that it is easy. Have you ever programmed an AI? If you have, you'll know that even a trivial improvement can take a lot of effort. Challenge of implementation is basically a non issue... its ASSUMED in AI development, and I can't imagine it getting simpler in a complex game like this.
Fact of the matter is, these are gaping holes in the AI's game, and they need to be fixed. While you can change the game rules to accomodate the AI, doing that too often and too dramatically waters down the game. I'd quite honestly prefer the AI to be improving its ability to prepare and initiate a war... areas where it's quite weak, which is why it is easy to exploit them there.