We present a theoretical analysis of O-2 adsorption on a reduced TiO2 (110) rutile surface, based on periodic ab initio Hartree-Fock calculations. Three different orientational approaches, three different spin symmetries, and two different adsorption sites are considered. We also consider the possibility that the surface can absorb more than one oxygen molecule. Positions of the surface ions, oxygen ions belonging to the third and fourth layers of the slab, and the bond lengths of the O-2 and O-2-substrate distances are optimized. Adsorption energies, admolecule-substrate bond lengths, spin densities and Mulliken charges are analyzed. The model is tested by comparing spin densities and relaxation parameters obtained for the reduced TiO2 (110) system to previous theoretical results. Finally, we discuss the relationship of our results to experimental observations of thermal desorption rates at low temperatures (100-600 K).