A detailed theoretical analysis of the free induction decay (FID) and spin echo (SE) MR signal formation in the presence of mesoscopic structure-specific magnetic field inhomogeneities is developed in the framework of the Gaussian phase distribution approximation. The theory takes into account diffusion of nuclear spins in inhomogeneous magnetic fields created by arbitrarily shaped magnetized objects with permeable boundaries. In the short-time limit the FID signal decays quadratically with time and depends on the objects' geometry only through the volume fraction, whereas the SE signal decays as 5/2 power of time with the coefficient depending on both the volume fraction of the magnetized objects and their surface-to-volume ratio. In the motional narrowing regime, the FID and SE signals for objects of finite size decay mono-exponentially; a simple general expression is obtained for the relaxation rate constant deltaR2. In the case of infinitely long cylinders in the motional narrowing regime the theory predicts non-exponential signal decay lnS approximately -tlnt in accordance with previous results. For specific geometries of the objects (spheres and infinitely long cylinders) exact analytical expressions for the FID and SE signals are given. The theory can be applied, for instance, to biological systems where mesoscopic magnetic field inhomogeneities are induced by deoxygenated red blood cells, capillary network, contrast agents, etc.