It has recently been demonstrated that nucleobase-density profiles of typical mRNA coding sequences exhibit a complementary relationship with nucleobase-interaction propensity profiles of their cognate protein sequences. This finding supports the idea that the genetic code developed in response to direct binding interactions between amino acids and appropriate nucleobases, but also suggests that present-day mRNAs and their cognate proteins may be physicochemically complementary to each other and bind. Here, we computationally recode complete Methanocaldococcus jannaschii, Escherichia coli and Homo sapiens mRNA transcriptomes and analyze how much complementary matching of synonymous mRNAs can vary, while keeping protein sequences fixed. We show that for most proteins there exist cognate mRNAs that improve, but also significantly worsen the level of native matching (e.g. by 1.8 viz. 7.6 standard deviations on average for H. sapiens, respectively), with the least malleable proteins in this sense being strongly enriched in nuclear localization and DNA-binding functions. Even so, we show that the majority of recodings for most proteins result in pronounced complementarity. Our results suggest that the genetic code was designed for favorable, yet tunable compositional complementarity between mRNAs and their cognate proteins, supporting the hypothesis that the interactions between the two were an important defining element behind the code's origin.