Now that I've read your post, I'd say that impurity is much more similar to "goto" than with object orientation.
A language with "goto" is not structured. It does not matter how often it's used, or how similar the rest of the language is to a structured one. The same is true for side effects.
(Funny thing that the most used language has both.)
If code is structured or not is not really a property of a language, every function call is effectively a "goto" although with more convenient syntax. If your functions are partitioned in a strange way, you can just as easily produce spaghetti code. Same with nested if statements. You can write well structured code in Fortran 77 for example, even though most standard control structures involve a goto. Absence of a goto statement is neither necessary nor sufficient for enforcing structured code. One real advantage is perhaps that the compiler has more invariants to work with.
There is an entire class of compiler optimizations that can only be done on structured languages. If you include a "goto" command in a language you must either do a huge amount of statical analysis to map your language into a structured one, or live without such optimizations.
The fact that some code do not use a feature of the language does not help the computer generating a faster program.
Also, no, function calls are not equivalent to "goto".
Compiler IL reduces all branches to the equivalent of "goto", so adding a few more is just no problem at all.
More important obstacles to optimization include use of exceptions (now that makes control flow complicated), memory aliasing (any write to a char * is a scheduling barrier), overly-defined int math (can't prove loop iteration count), and the fact that your compiler has no idea what the hell is going on inside an x86 chip anyway.
What you say is correct, though I would say that bundling up common patterns in syntactic constructs has direct advantage (you don't have to look carefully to make sure it actually fits the pattern you think it fits, &c).
Donald Knuth uses GOTO. It is perfectly safe if kept within a function: invoke a function, jump around like crazy inside it, exit to caller with return value. No problem.
Last I looked, jumping around like crazy was hard for compilers to follow and would cut short some optimization. Not an issue when Knuth was originally writing, much more of one today. It's possible that this has changed, though - it's been a while since I played with this in depth. There remains Dijkstra's issue that it can be hard for humans to follow in any event, which Knuth didn't really directly dispute - his position was that there remained some narrow use cases where the speed improvement was worth it, which is different than "jump around like crazy".
A language with "goto" is not structured. It does not matter how often it's used, or how similar the rest of the language is to a structured one. The same is true for side effects.
(Funny thing that the most used language has both.)