Oxygen abundances in a sample of ultra-metal-poor subdwarfs have been derived from measurements of the oxygen triplet at 7771-5 Å and OH lines in the near-UV performed in high-resolution and high signal-to-noise ratio spectra obtained with WHT/UES, Keck I/HIRES, and VLT/UVES. Our Fe abundances were derived in LTE and then corrected for non-LTE (NLTE) effects. The new oxygen abundances confirm previous findings for a progressive linear rise in the oxygen-to-iron ratio with a slope -0.33+/-0.02 from solar metallicity to [Fe/H]~-3. A slightly higher slope would be obtained if the Fe NLTE corrections were not considered. Below [Fe/H]=-2.5 our stars show [O/Fe] ratios as high as ~1.17 (G64-12), which can be interpreted as evidence for oxygen overproduction in the very early epoch of the formation of the halo, possibly associated with supernova events with very massive progenitor stars. We show that the arguments against this linear trend given by Fulbright & Kraft in 1999, based on the LTE Fe analysis of two metal-poor stars, cannot be sustained when an NLTE analysis is performed. We discuss how the Fulbright & Kraft LTE ionization balance of Fe lines underestimates the gravity of the very metal-poor star BD +23°3130 ([Fe/H]=-2.43) and how this leads to an underestimation of the oxygen abundance derived from the forbidden line. Gravities from Hipparcos appear to be in good agreement with those determined in NLTE, giving higher values than previously assumed, which reduces the discrepancies between the oxygen abundances determined from OH, triplet, and forbidden lines. Using one-dimensional models, our analysis of three oxygen indicators available for BD +23°3130 gives an average [O/Fe] ratio of 0.78+0.15-0.18. The high oxygen abundances at very low metallicities do not pose a problem to theoretical modeling since there is a range of parameters in the calculations of nucleosynthesis yields from massive stars at low metallicities that can accommodate our results. Based on data collected at the Keck I, VLT, and William Herschel telescopes.