The microstructures of sheared lherzolite xenoliths from South African kimberlites are investigated using new microstructural analysis techniques and new rheological data. By applying electron backscatter diffraction (EBSD) methods and the M-index technique for quantifying the strength of lattice preferred orientation (LPO), it is demonstrated that olivine and orthopyroxene, after an initial stage of dynamic recrystallization, deformed by different mechanisms: olivine deformed by dislocation creep, while orthopyroxene deformed by a grain-size sensitive mechanism that randomized the preexisting LPO. New rheological data, which incorporate the effects of pressure on deformation, are applied to these xenoliths. The effects of pressure are shown to dramatically reduce the inferred strain rates of these xenoliths in comparison to previous estimates. The contrasting microstructural features of olivine and orthopyroxene are analyzed using the Avrami theory of recrystallization, coupled with microstructural observations and experimental data. This analysis suggests that (1) the difference in the recrystallized grain-size and (2) the difference in the completeness of recrystallization, can be largely explained by the contrast in grain boundary mobility between olivine and orthopyroxene.