The key here lies in the fact that "state of the union" isn't just a phrase, it's a title - State of the Union - which is understood to be the name of a speech.
If we have multiple of those things, we don't want to pluralise the states, nor to we want to pluralise the unions: we want to pluralise the entire title - State of the Unions.
The fact that this happens to be the same as if we were trying to pluralise "unions" (e.g. in the sense that we were referring to a single address about multiple unions) is just an unfortunate side-effect. It's the context, however, that removes the ambiguity between "State of the Union(s)" and "State of the Union(s)".
"State of the Unions" implicitly refers to "State of the Union Addresses," in the same way that "Harry Potters" refers to "Harry Potter books," not a single book about multiple wizards of the same name (which would be very confusing).
Consider another example: "The Fast and the Furiouses." If "The Fast and the Furious" weren't a title, understood in-context to refer to a movie, you'd complain that "Furiouses" doesn't make sense. Of course, in reality, you wouldn't likely complain about this pluralisation (except possibly to suggest including the word 'movies'!)
Try writing each variation out in full, parenthesizing the omitted word (addresses) and then contracting to the shorthand from there.
- States of the Union (address) - States of the Union - one address about multiple states of a single union.
- State of the Unions (address) - State of the Unions - one address about the state of multiple unions.
- States of the Union (address)es - State of the Unions - multiple addresses about the state of a single union.
The confusion comes from the fact that these are three distinct concepts, two of which just happen to share a shorthand. The fact that there are "two potential nouns to pluralise" is a red herring - you want to pluralise the whole title.
Of course, it would be easier to avoid ambiguity altogether and simply say "State of the Union addresses."