As it stands, cloak is the ultimate invulnerability button, and I believe it shouldn’t be - I believe everyone should be vulnerable, anywhere. You can destroy the player owned stations to force people to undock or die. It won’t be done in a day, but anything but NPC stations can die. It is completely impossible to do anything against a cloaked ship in a SS, no matter how long you search for it - space is just that large (quick math - assume ship covers 1000km3/second, and I doubt you can even theoretically manage that right now - it will take ~10^21 seconds to cover 1au^3). Sure, he can’t do anything but move until he decloaks either, but this is besides the point - a person docked up can’t either, and he can blow up together with the station. Plus he undocks at a predictable point, unlike the cloaked ship which can pop up anywhere. So - lower risk, yet higher reward.
So, anti-cloak probes. Slow enough evasion is realistic and the cloaked ships can hunt.
For the NPC stations - make them semi-destructible. Attacking one spawns huge defender fleet of the station owner, while if you manage to destroy the station, you will only burn it down - trigger asset safety etc, as if a player station gets destroyed. But unlike player stations, in say a week or two, another same station would be rebuilt by the NPCs (having same everything).
I agree that something has to be done to local as well, but it is a tangentially related problem - it would be possible to nerf just local or just cloaks without making stuff more unbalanced than what cynos already offer. I find local in even more need of a nerf than cloaks, and out of suggestions I heard or had myself, by far the best I find the suggestion where you would hack the gate to have say 1 minute delay to appearing in local. It would solve the problem in a very neat way and unlike simpler nerfs, it would actually lead to new gameplay and addition to the current game. Much easier to justify that than simply swing a nerfbat there (similarly, that’s also why I prefer anti-covops probes to afk timer - one boosts counterplay, the other nerfs the module)
Finally, many are afraid of cloaked ships because they bring pain by hotdrops. A cloaked ship alone is not that much of a threat most of the time - you can fight it well enough because you are in a better ship for combat, even though he dictates the terms of fighting. When that 1v1 becomes 30v1, not so much. Hotdrops are even more of a problem when done defensively, because the only viable counter tactic (counterdrops) aren’t really an option. So, nerf that and all of a sudden cloaky “AFK?” players won’t be considered an issue anymore, even if you don’t touch local or cloaks. The best nerf would be to simply remove that - why would the biggest ships be the most mobile?