This expression must be compared with similar ones, like "the song of songs" or "the king of kings" (a title for Assyrian and Persian kings, also found in Ezra 7:12; Ezekiel 26:7; Daniel 2:37). There are many more examples, also extra-biblical. "The X of Xs" is a common Semitic expression to denote the most X-like X. It is a way to express the superlative in a language that does not have it as a morphological category.
Thus, what literally means "the heavens of the heavens" really means "the most heavenly heavens". It depends on what the translator finds the most prototypical feature whether they translate "the highest heavens", "the heavenliest heavens", "the godliest heavens", etc. "the heavens of the heavens" is just a calque (a direct translation, in this case disregarding the idiom).
The other issue here is that the heavens are plural (thus "the heavens of the heavens" in contrast to "the king∅ of kings"). But this is because in the common Mesopotamian world-view, the heaven is made up of three parts. Because of this, שׁמי always occurs in the plural, as I explained elsewhere. This is in principle unrelated to the idiom "the X of Xs". Translations that render "heaven of heavens" are interpreting this plural as a singular to match the modern western world-view.
This common world-view, with separate layers of heavens, presumably influenced translations rendering "the highest heavens", because the highest heaven would be where God resides.
