We present magnetization (M) and magnetoresistance (MR) data for a series of Sr2FeMoO6 samples with independent control on antisite defect and grain-boundary densities, which reveal several unexpected features, including a novel switching-like behavior of MR with M. These, in conjunction with model calculations, establish that the MR in Sr2FeMoO6 is dominantly controlled by a new mechanism, derived from the magnetic polarization of grain-boundary regions acting like spin valves, leading to behavior qualitatively different from that usually encountered in tunneling MR. We show that a simple and useful experimental signature for the presence of this spin-valve-type MR (SVMR) is a wider hysteresis in MR compared to that in M.