Sorry, didn't mean to confuse. You're right, only a few species entire genomes have been sequenced, but one doesn't need the entire genome to do phylogenetic analyses. Literally, tens of thousands of phylogenetic analyses have been published. In fact there are a couple of journals devoted entirely to phylogenetic analyses (Systematic Biology, Molecular Phylogenetics and Evolution)
You can be pretty confident that an experimenter would not be allowed to evaluate the published data in any biased manner. All acceptable biology journals are peer reviewed with a scientific board of editors and outside referees. There are certain assumptions associated with these analyses, though. Dis-cordance would be discovered and reported, and, in fact it has.
Well, genes crossing species is not so wild an idea that it is dismissed outright, and, in fact, as you have pointed out, we know it happens in bacterial species. The problem with eukaryotes, there's no mechanism to test. If we get a proposed mechanism for this type of transfer, we can test it.
Redundant genes are probably the source for new genes. In the complex of genes for histocompatibility, this is accepted.
I don't know anything about "optimization algorithms," but your statement, "tend to find local minimums rather than global best solutions," is what has been theorized by Wright's shifting balance theory. In this theory, one can envision an evolutionary landscape with adaptive peaks. A population reaching an adaptive peak (through evolutionary selective processes) would find it difficult to reach another adaptive peak in the landscape, even though it was higher (more adaptive) because selection would preclude crossing a "valley" to reach the new peak. If you came up with this idea independently, I am extremely impressed with your intellect and intuitiveness. Can't say I would have.
I don't know the different optimization schemes of which you speak, but the evolutionary mechanism of natural selection appears to be at work in bacteria, plants and animals. An alternative mechanism has been proposed in the neutral (or nearly neutral) theory of evolution. It appears that both processes are at work in both eukaryotes and prokaryotes.
We have a good idea about the rate of random mutation and it appears to be universal. The maintainence of the viral gene expression in humans could have a number of explanations which Cullne et al. do not go into in their paper, but there has been much theoretical work on the maintainence of genetic variation. It's important to note however, that, by being incorporated into the human genome, this gene is now on a different evolutionary trajectory defined by human selective constraints.