It has recently been proved that, in the presence of a static absorbing trap, Sisyphus random walkers with a restart mechanism are characterized by {\it exponentially} decreasing asymptotic survival probability functions. Interestingly, in the present compact paper we prove analytically that, in the presence of a moving trap whose velocity approaches zero asymptotically in time as $v_{\text{trap}}\sim 1/t$, the survival probabilities of the Sisyphus walkers are dramatically changed into inverse {\it power-law} decaying tails.