Well, my Agent Orange with 10 Per and 3 Agi and Paranoia able to see them, their non-targetable siluette.
You definitely need to use Cloacking Device first of all.
Second, I don't know exactly how mechanics work, but I noticed long ago, that if you will be close to a stealthed target, he/it will detect you much earlier then if you with same stealth rating against same target will try to detect it from almost the borderof LoS.
So, if you lost detection battle with someone, just stay as farther from them as you can, and you will detect them, but they won't detect you.
Also, I don't know if NV turned on help to detect stealthied targets faster in dark caves, wanted to ask this long ago, like years.