In this work, we explore the accuracy of post-Hartree-Fock (HF) methods and double-hybrid density functional theory (DFT) for the computation of solid-state NMR chemical shifts. We apply an embedded cluster approach and investigate the convergence with cluster size and embedding for a series of inorganic solids with long-range electrostatic interactions. In a systematic study, we discuss the cluster design, the embedding procedure, and basis set convergence using gauge-including atomic orbital (GIAO) NMR calculations at the DFT and MP2 levels of theory. We demonstrate that the accuracy obtained for the prediction of NMR chemical shifts, which can be achieved for molecular systems, can be carried over to solid systems. An appropriate embedded cluster approach allows one to apply methods beyond standard DFT even for systems for which long-range electrostatic effects are important. We find that an embedded cluster should include at least one sphere of explicit neighbors around the nuclei of interest, given that a sufficiently large point charge and boundary effective potential embedding is applied. Using the pcSseg-3 basis set and GIAOs for the computation of nuclear shielding constants, accuracies of 1.6 ppm for 7Li, 1.5 ppm for 23Na, and 5.1 ppm for 39K as well as 9.3 ppm for 19F, 6.5 ppm for 35Cl, 7.4 ppm for 79Br, and 7.5 ppm for 25Mg as well as 3.8 ppm for 67Zn can be achieved with MP2. Comparing various DFT functionals with HF and MP2, we report the superior quality of results for methods that include post-HF correlation like MP2 and double-hybrid DFT.