Probabilistic shaping (PS) is a promising technique to approach the Shannon limit using typical constellation geometries. However, the impact of PS on the chain of signal processing algorithms of a coherent receiver still needs further investigation. In this work we study the interplay of PS and phase recovery using the blind phase search (BPS) algorithm, which is widely used in optical communications systems. We first investigate a supervised phase search (SPS) algorithm as a theoretical upper bound on the BPS performance, assuming perfect decisions. It is shown that PS influences the SPS algorithm, but its impact can be alleviated by moderate noise rejection window sizes. On the other hand, BPS is affected by PS even for long windows because of correlated erroneous decisions in the phase recovery scheme. The simulation results also show that the capacity-maximizing shaping is near to the BPS worst-case situation for square-QAM constellations, causing potential implementation penalties.