Polarization-insensitive conversion of return-to-zero (RZ) ON-OFF keying (RZ-OOK) to RZ binary phase-shift keying (RZ-BPSK) has been achieved by cross-phase modulation (XPM) in a nonlinear birefringent fiber. This work presents a theoretical analysis of the dependence of format conversion on pump-probe detuning, and the pump state-of-polarization (SOP) that can fluctuate unpredictably in a realistic system. An investigation of the impact of pump polarization fluctuation on receiver sensitivity and receiver optimal threshold for the converted RZ-BPSK probe is also carried out. It was found that although the desired XPM-induced n phase shift can be achieved by launching both the RZ-OOK pump and the probe along the same birefringent axis of the fiber, the phase shift degrades to π/3 if the SOP of the RZ-OOK pump unpredictably switches to the other axis of the fiber, resulting in a large receiver sensitivity penalty fluctuation of 14 dB. By contrast, launching the probe at 45° relative to the birefringent axes can reduce the polarization-dependent receiver sensitivity penalty fluctuation to about 2 dB as the SOP of the RZ-OOK pump is swept over the Poincaré sphere. These conclusions are in good agreement with recently published experimental results.