I found the following paragraph from Mike Cohn’s “Agile Estimating and Planning”, a bit contradictory.
“You should re-estimate only when your opinion of the relative size of one or more stories has changed. Do not re-estimate solely because progress is not coming as rapidly as you’d expected. Let velocity, the great equalizer, take care of most estimation inaccuracies.”
I think Cohn actually meant to say that velocity would take care of our completion inaccuracies (progress not coming as rapidly as we’d expected), not necessarily of – as stated – our size estimation inaccuracies (our opinion of the relative size). To address the latter, as Cohn says, we might need to re-estimate.