The nearly-neutral theory of molecular evolution has been widely accepted as the guiding principle for understanding how selection affects gene sequence evolution. One of its central predictions is that the rate at which proteins evolve should negatively scale with effective population size (N(e)). In contrast to the expectation of reduced selective constraint in the mitochondrial genome following from its lower N(e), we observe what can be interpreted as the opposite: for a taxonomically diverse set of organisms (birds, mammals, insects, nematodes) mitochondrially encoded protein-coding genes from the oxidative phosphorylation pathway (mtOXPHOS; n=12-13) show markedly stronger signatures of purifying selection (illustrated by low d(N)/d(S)) than their nuclear counterparts interacting in the same pathway (nuOXPHOS; n~75). To understand these unexpected evolutionary dynamics, we consider a number of structural and functional parameters including gene expression, hydrophobicity, transmembrane position, gene-ontology, GC content, substitution rate, proportion of amino-acids in transmembrane helices and protein-protein interaction. Across all taxa, unexpectedly large differences in gene expression levels (RNA-seq) between nuclear and mitochondrially encoded genes, and to a lower extent hydrophobicity, explained most of the variation in d(N)/d(S). Similarly, differences in d(N)/d(S) between functional OXPHOS protein complexes could largely be explained by gene expression differences. Overall, by including gene expression and other functional parameters the unexpected mitochondrial evolutionary dynamics can be understood. Our results not only reaffirm the link between gene-expression and protein evolution, but also open new questions about the functional role of expression level variation between mitochondrial genes.