Pad your estimates, because you are typically going to have similar bugs (for similar projects), and you can account for those unknowns probablistically. You don't know the exact bugs that will be found, but you've already predicted that some will be found, so include that in your estimate.

Sometimes your test matrix is too big. But I agree: sometimes you have to move slower in order to go faster overall and have better estimates. Estimates have to take into account testing and regression testing, which most people don't so it can make you look slow if you start doing that.