We present a search for charged massive long-lived particles (CMLLPs) that are pair produced in p-pbar collisions at sqrt(s)= 1.96 TeV collected by the D0 experiment at the Fermilab Tevatron collider. Our result is a combination of two searches where either one or both CMLLPs are reconstructed in the detector. We select events with muon-like particles that have both speed and ionization energy loss dE/dx different from muons produced in p-pbar collisions. In the absence of evidence for CMLLPs corresponding to 6.3 fb-1 of integrated luminosity, we set limits on the CMLLP masses in several supersymmetric models, excluding masses below 278 GeV for long-lived gaugino-like charginos, and masses below 244 GeV for long-lived higgsino-like charginos at the 95% C.L. We also set limits on the cross section for pair production of long-lived scalar tau leptons that range from 0.04 pb to 0.008 pb for scalar tau lepton masses of 100 to 300 GeV.