With a view to improving the consistency of free energy perturbation calculations in Monte Carlo simulations of protein-ligand complexes, we have implemented the replica exchange with solute tempering (REST) method in the MCPRO software. By augmenting the standard REST approach with regular attempted jumps in selected dihedral angles, our combined method facilitates sampling of ligand binding modes that are separated by high free energy barriers and ensures that computed free energy changes are considerably less dependent on the starting conditions and the chosen mutation pathway than those calculated with standard Monte Carlo sampling. We have applied the enhanced sampling method to the calculation of the activities of seven non-nucleoside inhibitors of HIV-1 reverse transcriptase, and its Tyr181Cys variant, and have shown that a range of binding orientations is possible depending on the nature of the ligand and the presence of mutations at the binding site.