Which proteins are part of the most different protein complexes?
This answer does not address the number of complexes that a protein participates in, but rather a related question -- With how many proteins does a protein interact?
I acknowledge this  is a fundamentally different question, though I think it's a good starting point on which other people can build a better answer.

Taking the data from STRING v11 for all protein-protein interactions (PPIs) in Escherichia coli str. K-12 substr. MG1655, we can subset these PPIs to include only those of action type &quot;binding&quot;.  This database provides PPI scores between 0 and 1 based upon experiments (co-purification, co-crystallization, Y2H), textmining, co-occurence, co-expression, and co-localization of coding genes across genomes.
If we set no cutoff for the confidence in these binding interactions, we see that 2585 proteins have ≥1 binding partner, and one protein has an astonishing 273 binding partners (pfo, a putative pyruvate-flavodoxin oxidoreductase).  Also, this database states this E. coli strain has 4127 distinct protein-coding genes, so approximately 63% (2585/4127) of genes encode a protein that interacts with at least one other distinct protein.
If we limit the interactions to those with a &quot;high confidence&quot; score (≥0.900), only 656 proteins (~16%) are seen to have ≥1 binding partner, with a maximum of 55 binding partners seen for 4 proteins.  Unsurprisingly, and consistent with the comment from Maximilian Press, these proteins are all associated with the ribosome (sra, rpsP, rpsI, and rpsR).  The spike in the graph below at 54 interacting partners for the high-confidence PPIs is a group of of ribosomal proteins, most of which are annotated as co-interactors.

Two important notes on interpretation of interactions in this database:

splice variants and post-transcriptionally modified proteins are collapsed into single nodes in the interaction network, so all gene product variants are represented by one coding sequence
self-interactions (e.g. dimerization) are not counted, which are a valid type of protein complex per the question