The diffusion properties of water in polyelectrolyte multilayers (PEM) are investigated by pulsed field gradient diffusion NMR. The dependence of the mean-square displacement on the observation time does not agree to Gaussian diffusion, suggesting restricted diffusion in a porous structure. However, the extraction of a pore size in a model of restricted diffusion yields a very large pore size of several micrometers. The additional influence of cross-relaxation of water and polymer spins is investigated in Goldman-Shen experiments. These demonstrate a strong influence of cross-relaxation rates on diffusion echo decays, such that pore sizes obtained from the model of restricted diffusion have to be corrected. Corrected pore sizes are about 4 microm and reflect the existence of domains of lower polymer density and thus faster water diffusion. These heterogeneities occur upon PEM preparation at high salt content for large layer numbers and are detected in the surface morphology, too.