The thing we must remember is that during evolution, there occurs many events that may result in genomic reshuffling.
Considering your example of MHC, when we look into the evolution of the complexes
The classical human MHC contains 224 genes, .... Antibody and T cell mediated immune responses against invading pathogens are initiated through MHC class I and class II molecules. These main components are not only missing from invertebrates, but are also not present in primitive jawless fish, such as hagfish and lamprey. MHC class I and II molecules do, however, exist in all jawed vertebrates, including the cartilaginous fish.
Now that tells us something in itself. If you observe the universal evolutionary tree, we can conclude that the hagfish and lamprey are most ancestral, especially compared to telostii. This is crucial when speaking in terms of evolution, as
this demonstrates that the separation of the MHC class I and class II loci is characteristic of teleost fish, which represent half of all vertebrates. Since the genes of the immune system were present in the common ancestor of tetrapods and teleosts, the differences in their genomic organisation may be the result of lineage-specific chromosomal events such as duplications, inversions, deletions and translocations.
You can read more about the MHCs here:
Sambrook, Jennifer G., Felipe Figueroa, and Stephan Beck. "A genome-wide survey of Major Histocompatibility Complex (MHC) genes and their paralogues in zebrafish." BMC genomics 6.1 (2005): 152.
And thats usually the reason for the major changes you see. Often other changes occur, due to transposons, which cause pseudogenes to form and/or neofunctionaliation to occur. You can read about them here:
Feschotte, Cédric, and Ellen J. Pritham. "DNA transposons and the evolution of eukaryotic genomes." Annual review of genetics 41 (2007): 331.
I am fairly certain, that this applies practically to majority of the genes, that are not linked strongly genetically (http://learn.genetics.utah.edu/content/pigeons/geneticlinkage/).