Mining the Galactic halo for very metal-poor stars