Gamma-ray observations by the Fermi Large Area Telescope have been used very successfully in the last 9 years to detect more than 200 gamma-ray pulsars. Sixty of these have been found by directly searching for pulsations in the gamma-ray data, but only one binary MSP has been found this way. Pulsars in binaries are often difficult to detect in radio data because of large eclipses, and some binary MSPs may even be radio quiet. For those, a gamma-ray blind search might be the only possibility for detection. While searches for isolated pulsars up to kilohertz frequencies are already computationally very challenging, blind searches for binary gamma-ray pulsars are simply infeasible without further knowledge of their orbital parameters. We present methods with which we can conduct searches for candidate binary gamma-ray pulsars for which orbital constraints are known from optical observations of a likely companion star. We also highlight some example sources where these methods have been used. Additionally, some redback MSPs can be more easily timed in gamma rays than with radio observations.