From what I am gathering from a few places, the deep strike "punish" mechanic is really hurting some clever strategies and mobile support units, like this one for example.
As someone else has pointed out, one of the original intents of the deep strike mechanic was to prevent very minimalistic styles of play from being brokenly good, but that purpose is largely served by core shield generators, which accomplish that in a much more direct way.
However, given that core shield gens are optional, and this deep strike mechanic is not, I think the deep strike mechanic should stay, but become much less intense. Like up the distance needed to trigger it to like 8 planets or something. Or maybe up it to 6 planets, but on the 7th planet, the rate the AI responds will be barely noticeable (like, say, only enough to match the strength of 10 Mk. II fleet ships per 20 seconds or something pathetic like that), but then increase the response when going even further out (so like 10 planets out, the AIs response is in full force)
As always, exact numbers subject to adjustment.
EDIT: For reference, the current distance is 4 planets, which means at 5 planets out, you start getting extra spawns from the AI. That is a bit short IMO