I think the placement in the sentence makes the difference. “I’m sure” at the beginning is questioning; “I’m sure” at the end emphasizes.
The actual words don’t matter than much. Whatever they are, at any level of formality, they’re just examples of social lubricants. English is filled with semantically meaningless noises that are inserted to acknowledge that the other person in a conversation is a social equal, not a servant.
The evolution is, I believe, actually from the other direction, in which a peon would have to address a noble with “Sir/Madam” or “My Lord/Lady” or “Liege.” So the peerage, i.e. the nobles and the upper classes, would use elaborate etiquette when addressing one another to show that they were peers, i.e. equals, and not part of the rabble. Over time, the rising middle classes started imitating them and dropped in phrases of their own to show they were above the working class. The lateness of “charmed” - “Charmed (short for I am charmed) as a conventional reply to a greeting or meeting is attested by 1825.” - is an indicator that it comes from the middle and not upper classes.
Americans like to pretend that they are part of a classless society. Certainly true that we never had an actual nobility, but the middle class that rose in the 19th century copied huge amounts of British social conventions. The form of the mouthnoises keeps changing over time but their reason is fixed in the language.
I was in a production of Annie Get Your Gun in high school. My one line, upon meeting someone, was “Charmed, I’m sure.” It’s my sole contribution to the theater arts.
These phrases are ultimately meaningless; they’re what you say in certain social situations. Right now, “No problem” is taking over from “You’re welcome” and there’s nothing that anyone can do about it. Logic and reasoning has little to do with it.
In ten years, it may be as quaint as saying “Glad to know you” when introduced.
Fozzie shows Kermit his different recycling categories, which are “BOTTLES”, “CANS”, “PAPER” and “SNOO”. Kermit asks, what’s snoo? Fozzie responds with “Nothing, what’s “snoo” with you?”
I still remember that TV spot over 30 years later.
For those who are having kneejerk reactions to the level of comedy in the 1940s, It Pays to Be Ignorant was a spoof, featuring “a board of experts who are dumber than you are and can prove it”.
There’s no excuse for the rest of the quotes, though.