I'm not a fan of hidden units with attack capabilities at all. However, in my time with FFH2, I've thought of one system that would make it more enjoyable than the Either You've Got a Counter-Spy or You Don't system.
First, units such as Shadows do not have the ability to attack. They do have an assassinate ability, much like a cast spell. They can use the ability on any other unit on the same tile (as a targetable spell). There are two measures of success. Their ability to damage and/or kill their target (which may involve damage and/or death for themself) and their ability to stay hidden after the assassination attempt. The latter concern could depend on the number of enemy units in the same tile, the strength of enemy units in the same tile, the type of enemy units in the same tile (e.g., a marksman unit could have a high probability of discovering a shadow as opposed to its current ability), and perhaps other considerations (e.g., buildings, spells,...). If the shadow fails to stay hidden, he is booted from the tile in a random direction and stays visible until his next turn.
There would also be a way to try to hunt down a shadow when they are hidden. I'm not sure of how this could be implemented without clogging the UI or automatically giving away the presence of a shadow but, perhaps, units in any friendly city would get the ability to search the city for hidden enemies, much like the lock-down mentioned already in this thread. Each attempted spy-hunt would cost the unit's movement and have a chance to succeed based on the "hunter's" current strength and the shadow's current strength, perhaps with a bonus for any previous hunting attempts within the same city that were performed this turn. Certain units, such as marksmen, would get a bonus to find hidden enemies and would also have this 'hunting' ability enabled outside of city limits.
Anyway, that's what crosses my mind whenever I have to deal with Shadows.
- Niilo