We present the results of a variable-temperature (VT) 31P magic angle spinning NMR (MAS-NMR) study of a series of solid solutions between different synthetic rare earth (RE = Y, La, Ce, Pr, Nd, Eu, Dy) orthophosphates (REPO4) taking either the monoclinic monazite or tetragonal xenotime (zircon) crystal structure. Solid solutions were formed by mixing a small amount of a paramagnetic REPO4 material (RE = Ce, Pr, Nd, Eu, Dy) with either diamagnetic LaPO4 or YPO4, which take the monoclinic and tetragonal crystal structures, respectively. Mixtures were made with up to 10 mol% (nominal content) of the paramagnetic component. 31P spectra of these materials contained several paramagnetically shifted resonances indicating some dissolution of the paramagnetic rare earth into the host LaPO4 or YPO4 phase; however, it is clear that none of the samples studied here reached a state of complete solid solution. The use of multiple paramagnetic species in dilute solid solution with two diamagnetic materials taking different crystal structures enabled an investigation of the probable mechanisms of paramagnetic interactions in the 31P NMR experiments. A peak assignment model is introduced for the 31P spectra. Our analysis indicates that the paramagnetic interactions are dominated by the Fermi contact shift with a secondary contribution from the so-called “pseudocontact” shift.