There seem to be a couple of confusions here. First, evolution is not a global optimization algorithm; all species are in the vicinity of local optima, not some global optimum (if that even means anything biologically).
This is true. It doesn't really affect the argument, however.
Second, while evolution is stochastic, it is strictly a local search procedure, at least in metazoans. Evolution will explore slightly suboptimal solutions, but strongly suboptimal ones will never last long enough for a species to move through that trough, and lethal solutions are impassible. Are there workable paths between the regions of viability? That question can only be answered empirically at this point, not by the kind of abstract argument you're using here.
I agree. I also agree with your point that we can only deduce that evolution works in nature through empirical observation; you are correct (AFAIK) in stating that we cannot say from first principles alone whether or not a certain hypothetical branch of evolution is feasible.
When it comes to not exploring strongly suboptimal solutions, that is correct in a stable environment. However, if the environment changes relatively drastically (as it does every now and then), the current configuration of genomes will be strongly suboptimal and the search for new minima will be swift and highly stochastic. It's a bit like annealing in that way; the closer the system gets to a minimum, the lesser the stochastic factor becomes.
Larger jumps (large insertions and deletions, for example) are possible, but as their effect gets larger, the probability of their hitting a viable solution drops sharply. This is true not only because the great majority of genome space is not viable (so picking random points is a very bad strategy), but also because offspring inherit not only a (possibly modified) genome from their parents, but also a developmental environment (e.g. the chemical environment of a fertilized egg). That environment is unlikely to support development of a very different organism.
Very true. I agree with all of your points. However, it should be noted that most changes in the genome - even large changes - does not hinder the possibility to reproduce. As long as the reproductive systems themselves remain relatively unaltered (as they have for a very, very long time), we can get away with all sorts of large-scale changes in the individual - even entire missing (or added) chromosomes. The chances of such a mutation to be beneficial is, as you say, vanishingly small so you are correct in stating that there needs to be a reasonable "path" between any two points in the evolutionary history of a species. And there is; that's why we get a nested hierarchy.
So basically, I agree with you: we cannot, from a quick look at the evolutionary process, determine whether or not a certain hypothetical evolutionary path is viable. That, however, is not an argument against macroevolution, because the empirical evidence to compensate for this is available, thanks to paleontology and comparative genetics.