In Paper I of this series the formulations of the replica-exchange multicanonical algorithm and the multicanonical replica-exchange method for Monte Carlo versions have been presented. The effectiveness of these algorithms were then tested with the system of a penta peptide, Met-enkephalin, in the gas phase. In this article the detailed comparisons of performances of these algorithms together with the regular replica-exchange method are made, taking a more complex system of a 17-residue helical peptide. It is shown that these two new algorithms are more efficient than the regular replica-exchange method. (C) 2003 American Institute of Physics.