Recently, it has been found that the tree-level CP invariance of the Higgs potential in the minimal supersymmetric standard model (MSSM) can be sizeably broken by loop effects of soft-CP-violating Yukawa interactions related to scalar top and bottom quarks. Within this framework, the one-loop CP-non-invariant renormalization-group improved effective potential is calculated, including leading logarithms due to two-loop Yukawa and QCD corrections. The CP-violating parameters of this scenario may be constrained by considering the new two-loop contributions to the electron and neutron electric dipole moments (EDMs). After implementing these new EDM constraints, the three neutral Higgs particles are predicted to strongly mix with one another and significantly modify their tree-level couplings to fermions and to the W± and Z bosons. The phenomenological consequences of such a minimal supersymmetric scenario of explicit CP violation on the production rates of the lightest Higgs particle and on its potential discovery at LEP2 and an upgraded Tevatron machine are discussed.