We present a reinvestigation of sulfate-water clusters SO4(2-) (H2O)(n=3-7), which involves several new aspects. Using a joint molecular mechanics/first principles approach, we perform exhaustive searches for stable cluster geometries, showing that the sulfate-water landscape is much richer than anticipated previously. We check the compatibility of the new structures with experiment by comparing vertical detachment energies (VDEs) calculated at the B3LYP/6-311++G** level of theory and determine the energetic ordering of the isomers at the RI-MP2/aug-cc-pVTZ level. Our results are bench-marked carefully against reference energies of estimated CCSD(T)/aug-cc-VTZ quality and VDEs of CCSD(T)/aug-cc-pVDZ quality. Furthermore, we calculate anharmonic vibrational corrections for up to the n = 6 clusters, which are shown to be significant for isomer energy ordering. We use energy decomposition analysis (EDA) based on the absolutely localized fragment (ALMO) expansion to gain chemical insight into the binding motifs.