Numerous affinity purification - mass-spectrometry (AP-MS) and yeast two hybrid (Y2H) screens have each defined thousands of pairwise protein-protein interactions (PPIs), most between functionally unrelated proteins. The accuracy of these networks, however, is under debate. Here we present an AP-MS survey of the bacterium Desulfovibrio vulgaris together with a critical reanalysis of nine published bacterial Y2H and AP-MS screens. We have identified 459 high confidence PPIs from D. vulgaris and 391 from Escherichia coli. Compared to the nine published interactomes, our two networks are smaller; are much less highly connected; have significantly lower false discovery rates; and are much more enriched in protein pairs that are encoded in the same operon, have similar functions, and are reproducibly detected in other physical interaction assays. Our work establishes more stringent benchmarks for the properties of protein interactomes and suggests that bona fide PPIs much more frequently involve protein partners that are annotated with similar functions or that can be validated in independent assays than earlier studies suggested.