def getOrThrow[T](x: Option[T]): T = x.getOrElse(throw new AirlineError)

    def findFlight(code: AirlineCode, constraints: Constraints) = for {
      airline <- findAirline(code).map(getOrThrow)
      flights <- getFlightsForToday(airline)
      available <- findAvailable(flights, constraints).map(getOrThrow)
    } yield (available)

No idea why you consider using scalaz to be cheating.