In early 2000, it was shown that it is possible to develop exact sampling schemes for a large class of parametric non-bandlimited noiseless signals, namely certain signals of finite rate of innovation. In particular, signals x(t) that are linear combinations of a finite number of Diracs per unit of time can be acquired by linear filtering followed by uniform sampling. However, when noise is present, many of the early proposed schemes can become ill-conditioned. Recently, a novel stochastic algorithm based on Gibbs sampling was proposed by Tan & Goyal [IEEE Trans. Sign. Proc., 56 (10) 5135] to recover the filtered signal z(t) of x(t) by observing noisy samples of z(t). In the present paper, by blending together concepts of evolutionary algorithms with those of Gibbs sampling, a novel stochastic algorithm which substantially improves the results in the cited reference is proposed. (C) 2009 Elsevier B.V. All rights reserved.