The Poincaré recurrence statistic (PRS) measures the probability that a trajectory initiated in a phase space region will first return to that region, as a function of time. For deterministic, area-preserving maps with a mixture of regular and chaotic orbits, the stickiness of invariant tori and islands is responsible for a power-law decay in the PRS. We show that noise perturbations allow trajectories to access the interior of islands, enhancing their trapping effect and causing many orbits to take longer to return to a neighborhood of their initial conditions. The noisy PRS can then exhibit an extended tail on an intermediate time scale, which is eventually followed by an asymptotic exponential decay. We study a typical example, the Harper map, and compare distributions of trapping and visit times to islands with recurrence times to show the importance of noise in creating tails in the PRS. A simple finite-state Markov model of the dynamics confirms how this slower decay can be caused by noise permitting entry to previously inaccessible regions.