We present periodic "DFT+U" studies of single oxygen vacancies on the CeO2(110) surface using a number of different supercells, finding a range of different local minimum structures for the vacancy and its two accompanying Ce(III) ions. We find three different geometrical structures in combination with a variety of different Ce(III) localization patterns, several of which have not been studied before. The desired trapping of electrons was achieved in a two-stage optimization procedure. We find that the surface oxygen nearest to the vacancy either moves within the plane towards the vacancy, or rises out of the surface into either a symmetric or an unsymmetric bridge structure. Results are shown in seven slab geometry supercells, p(2 x 1), p(2 x 2), p(2 x 3), p(3 x 2), p(2 x 4), p(4 x 2), and p(3 x 3), and indicate that the choice of supercell can affect the results qualitatively and quantitatively. An unsymmetric bridge structure with one nearest and one next-nearest neighbour Ce(III) ion (a combination of localizations not previously found) is the ground state in all (but one) of the supercells studied here, and the relative stability of other structures depends strongly on supercell size. Within any one supercell the formation energies of the different vacancy structures differ by up to 0.5 eV, but the same structure can vary by up to similar to 1 eV between supercells. Furthermore, finite size scaling suggests that the remaining errors (compared to still larger supercells) can also be similar to 1 eV for some vacancy structures.