In the IEEE 1588 Precision Time Protocol (PTP), the recovery of clock frequency and phase from packet timestamps must be modeled as a statistical estimation problem, due to the random nature of end-to-end delays that is inherent to packet-switched networks. Recently, a new minimax optimum estimator for phase offset estimation was proposed by the authors. This approach assumes that perfect frequency synchronization is already available at the slave clock. In this paper, we show that when perfect frequency synchronization is unavailable, this estimator can be extended to jointly estimate clock phase and frequency offsets. The mean squared error of these estimators can be used to obtain fundamental limits on synchronization accuracy in such scenarios. Simulation results indicate that the proposed estimators provide significant performance benefits over conventional frequency and phase estimation techniques.