I like the long range but one at a time decloaker thing. Make it like the counter spy, targets cloaked ships only but at a huge range, but instead of insta-killing them, it decloaks them (for the same amount of time as normal decloaking). Of course, it would cost MUCH less than a counter spy, have a much greater recharge time, and a moderate knowledge unlock cost. Maybe with a ship cap of 3 or something, so you can reasonably get rid of "waiting" cloaked stuff in border worlds and still build some to stop those occasional cloaked ships that sneak in and "park" in your home world or core worlds. Up to you whether scouts and scout-starships should be immune, but it definitely should not target those immune to tachyon beams. Also, it is up to you whether the base AI gets some of these or not. (The AI that uses many counter-spies should also get even more of these though)
Now to address some possible criticisms:
Does this completely null the strategy of the AI "parking" cloaked units?
No, as you have very small number of them you can build, and thus you have to choose which planets get them wisely. Also, although they would be cheaper than a counter-spy, they still will be pretty expensive and lengthy to build so that players don't freely "juggle" them between planets. This way, if the AI manages to sneak into a planet that does not have one, it will still be a hassle to "move" one there. Plus the slow refire rate means that if there are many cloaked ships, it will take some time reveal all of them. Of course, the cloaked ships would realize they are in danger if there is one or even one being built, and thus be more likely to risk an attack or a retreat, so you may get attacked anyways.
Does this make other decloaking methods significantly less useful?
No, because of the slow firing rate, the low cap, and the "only one at a time" thing. Conventional decloakers can still reveal everything in their range all at once, thus being much better for the area they cover. Admittedly, planets with military Mk. III command stations would not need these, but military Mk. III command stations would be much harder to get (knowledge wise), and if IIRC, also suffer from a ship cap (only Mk. I command stations don't have a cap). Tachyon warheads will still be a quicker (albeit dirtier) way to decloak ships, if you can handle the whopping 1 AIP it adds.
If the AI does get them, and they would be able to target scouts, does that make scouting too hard?
Possibly, but like counter-spies, they would be quite (but maybe not quite as) rare. The exception would be that AI type that gets counter-spies, which would also get many of these. But then again, it is already hard to scout against one of these, so no major additional hassle is introduced. Also, unlike counter-spies, they obey tachyon-beam immunity, so they would be unable to decloak Mk. IV scouts and Mk. IV scout starships.
Anyways, should this be copied to the bugtracker as a suggestion?
EDIT: Doh, didn't see that the OP already had a suggestion. In my completely biased opinion, I like my idea better, but we can discuss which one would work better, or maybe even if neither would work.
EDIT2: If no one says I should or should not post this idea in the bug tracker in about an hour, I'll go ahead and post it.
EDIT3: I just posted it,
http://www.arcengames.com/mantisbt/view.php?id=2260