I think it's a good idea to get information about people entering and exiting an encounter (when they're not sneaking).
Not sure how scripting works, but perhaps there could be a roll for everyone allready in the encounter based on Perception and Outdoorsman. Each player allready in the encounter would get a different chance of detecting people entering.
Also, someone who enters can enter undetected if his Sneak, Agility and/or outdoorsman is high enough? Or link it to support perks with fitting requirements.