I had a similar problem when ran into a Rebel w *60* Evasion. (don't remember his traits, but "normal" Rebels had 10 EV)
He was nearly *Impossible* to kill (on as "EASY" Quest!) & took several of my chars!