In this study, we explore the use of nondeterministic search trajectories to accomplish a two-fold mission of mobile robot search for a stationary target while avoiding counter-targeting by the adversary throughout the operation. We analyze the characteristics associated with a Levy distribution of search leg lengths to generate appropriate randomized search trajectories. We discuss the alteration of the probability distribution of the Levy search as a result of the method utilized to best address the presence of the bounded search area and confine the searcher within its boundaries. Through regression analysis of simulation results, we determine expressions for the coverage ratio evolution of the modified Levy search strategy and the distribution on time to target detection TD, from which we are able to calculate the expected time, E[TD], to detect the target uniformly distributed within the search area. We assert assumptions regarding the adversary's detection and tracking abilities to estimate the expected time, E[TC], required for it to counter target the searcher. From these two expected times, we construct a novel probabilistic mission performance metric that measures the likelihood that the searcher will detect the target before it is counter targeted itself.