We present P-31 magic angle spinning nuclear magnetic resonance spectra of flux-grown solid solutions of La1-xCexPO4 (x between 0.027 and 0.32) having the monoclinic monazite structure, and of Y1-xMxPO4 (M = Vn+, Ce3+, Nd3+, x between 0.001 and 0.014) having the tetragonal zircon structure. Paramagnetically shifted NMR resonances are observed in all samples due to the presence of paramagnetic Vn+, Ce3+, and Nd3+ in the diamagnetic LaPO4 or YPO4. As a first-order observation, the number and relative intensities of these peaks are related to the symmetry and structure of the diamagnetic host phase. The presence of paramagnetic shifts allows for increased resolution between NMR resonances for distinct atomic species which leads to the observation of low intensity peaks related to PO4 species having more than one paramagnetic neighbor two or four atomic bonds away. Through careful analysis of peak areas and comparison with predictions for simple models, it was determined that solid solutions in the systems examined here are characterized by complete disorder (random distribution) of diamagnetic La3+ or Y3+ with the paramagnetic substitutional species Ce3+ and Nd3+. The increased resolution given by the paramagnetic interactions also leads to the observation of splitting of specific resonances in the P-31 NMR spectra that may be caused by local, small-scale distortions from the substitution of ions having dissimilar ionic radii.