Why not just make it so that cloaks won't work within 5K of other players, including an automatic de-cloak when players get within range? Sort of like simple sneak mechanics from a bunch of other games, including multiplayer games, and it seems to have been working out alright for a decade or so of gaming.
The cloak user still gets 5K range on their prey, and they can catch up and CD before the other party will be able to enter cruise. The other party will have a few seconds to prepare when they see a baddie appear at 5K range, so no more insta'ing. There'll be a little more fun to it as a cloak user as you have to rely a little on guile and skill, in that you have to be able to keep other players at 5K to maintain stealth. More fun all round.