It's all about the context
My answer started out as a comment, but then it evolved until I think it justifies consideration on its own. It remains primarily in response to other answers, but my perspective I think is broader and more useful.
I completely disagree with the various ideas that "same" must imply unalterable, literal "exactness" or a state of being "identical", primarily because in very many cases which one might consider "literal" or "exact", it is still only within a certain context. Imagine if both shirts (borrowed from another answer) have the same color, same buttons, some collar, same everything that you might think of in the moment... so that in your context they are exactly, literally the same. You may well be justified in simply calling them the "same" without any extra modifier whatsoever. You could insist that "exact/exactly" is redundant and unnecessary. What if I then expanded the context and asked which shirt was dry cleaned and which not (assuming that only one was dry cleaned)?
Perhaps then, if like so many who insist that adding a modifier to "same" is absolutely redundant, you say
"Oh, well I guess I was just wrong then. They are not the same now in the new context and so they were never the same to begin with. It was only my ignorance that kept my statement from being correct or from having a 'literal' meaning. Instead the shirts always were and must remain merely similar."
We could continue playing that game until even the meaning and usefulness of "literal" or "exact" begins to be questioned. But before we get that far, I assert that we can never box in words like "same", since there is probably always an expanded context in which the meaning of those words are only relative (unless, perhaps, you are omniscent).
So the perfectly acceptable use of modifiers (and frankly I don't care which form... "exactly the same" or "exact same") is simply a way of expressing a comparison between two contexts. In one context they are "the same", perhaps with never the need to consider more. But from the perspective of an expanded context, "exactly the same" implies that something continues to be identical, even when the expanded context introduced the possibility of destroying the "same-ness".
In short, there is nothing wrong with using these phrases, and anyone who argues against it probably has not thought long and hard enough about the broader context in which we all think or speak... and this even applies to English teachers.
My perspective originally developed from the use in describing computer programming constructs. It would get rather old if I could never call anything "the same" without implying precise, unvarying exactness. Likewise, it would be extremely unproductive if I always had to use only the word "similar" followed by a long list of qualification for what degree of similarity. Instead, I establish a context: I first declare (or let it be naturally implied by people with my same mindset) what particular set of properties I am discussing at the moment. Then I freely use words like "the same" to mean "all of the properties in my limited context are identical". But then if I need to expand the context while still holding the previous context in consciousness... I use the wonderfully simple, useful, short phrase "exactly the same" to now imply that not only is the limited set of properties identical, all other properties in the expanded context are also identical. Wow! It's amazing what a simple word can do in avoiding having to be ridiculously verbose.