We experimentally investigate the first-order polarization-mode dispersion (PMD) tolerance of two polarization-multiplexed (POLMUX) RZ-DQPSK signals at overall 40 Gb/s. The polarization demultiplexing is enabled by an automatic endless polarization stabilizer. Time-interleaving the two orthogonally polarized RZ-DQPSK signals minimizes the crosstalk due to the non-ideal polarization stabilization, while it represents the worstcase for the PMD-induced crosstalk. Bit-error rate measurements are performed both in back-to-back and after 25-km standard single-mode fiber. The PMD tolerance is evaluated as a function of the instantaneous differential group delay, introduced by a first-order PMD emulator. 40-Gb/s POLMUX RZ-DQPSK is more sensitive to PMD than single-polarization 20-Gb/s DQPSK, while it is more PMD-tolerant than 40-Gb/s NRZ-OOK. Besides, its chromatic dispersion robustness is similar to the single-polarization 20-Gb/s DQPSK. The combination of POLMUX and DQPSK is therefore very promising in view of transmission systems at high bit-rate.