The ultimate bound to the accuracy of phase estimates is often assumed to be given by the Heisenberg limit. Recent work seemed to indicate that this bound can be violated, yielding measurements with much higher accuracy than was previously expected. The Heisenberg limit can be restored as a rigorous bound to the accuracy provided one considers the accuracy averaged over the possible values of the unknown phase, as we have recently shown [Phys. Rev. A 85, 041802(R) (2012)]. Here we present an expanded proof of this result together with a number of additional results, including the proof of a previously conjectured stronger bound in the asymptotic limit. Other measures of the accuracy are examined, as well as other restrictions on the generator of the phase shifts. We provide expanded numerical results for the minimum error and asymptotic expansions. The significance of the results claiming violation of the Heisenberg limit is assessed, followed by a detailed discussion of the limitations of the Cramer-Rao bound. ; Comment: 22 pages, 4 figures