A search is presented for physics beyond the standard model (BSM) in events with a Z boson, jets, and missing transverse energy (MET). This signature is motivated by BSM physics scenarios, including supersymmetry. The study is performed using a sample of proton-proton collision data collected at sqrt(s) = 7 TeV with the CMS experiment at the LHC, corresponding to an integrated luminosity of 4.98 inverse femtobarns. The contributions from the dominant standard model backgrounds are estimated from data using two complementary strategies, the jet-Z balance technique and a method based on modeling MET with data control samples. In the absence of evidence for BSM physics, we set limits on the non-standard-model contributions to event yields in the signal regions and interpret the results in the context of simplified model spectra. Additional information is provided to facilitate tests of other BSM physics models.