We investigate on small world networks (SWN's) the survival probability of immobile targets, which get annihilated by random walkers at first encounter. On SWN's we find (distinct from regular lattices, Cayley trees, and regular ultrametric spaces) that in general the survival probability cannot be directly related to the average number of distinct sites visited. We underline this finding with arguments related to the structural disorder of SWN's and through the derivation of a lower bound for the targets' decay.