Recent calculations of gravitational radiation recoil generated during black-hole binary mergers have reopened the possibility that a merged binary can be ejected even from the nucleus of a massive host galaxy. Here we report the first systematic study of gravitational recoil of equal-mass binaries with equal, but anti-aligned, spins parallel to the orbital plane. Such an orientation of the spins is expected to maximize the recoil. We find that recoil velocity (which is perpendicular to the orbital plane) varies sinusoidally with the angle that the initial spin directions make with the initial linear momenta of each hole and scales up to a maximum of ~4000 km/s for maximally-rotating holes. Our results show that the amplitude of the recoil velocity can depend sensitively on spin orientations of the black holes prior to merger.