Complete one-loop results for the decay widths of neutral Higgs bosons (h_a) into lighter neutral Higgs bosons (h_b, h_c) are presented for the MSSM with complex parameters. The results are obtained in the Feynman-diagrammatic approach, taking into account the full dependence on the spectrum of supersymmetric particles and all complex phases of the supersymmetric parameters. The genuine triple-Higgs vertex contributions are supplemented with two-loop propagator-type corrections, yielding the currently most precise prediction for this class of processes. The genuine vertex corrections turn out to be very important, yielding a large increase of the decay width compared to a prediction based on the tree-level vertex. The new results are used to analyse the impact of the experimental limits from the LEP Higgs searches on the parameter space with a very light MSSM Higgs boson. It is found that a significant part of the parameter space of the CPX benchmark scenario exists where channels involving the decay h_2 --> h_1 h_1 have the highest search sensitivity, and the existence of an unexcluded region with M_{h_1} approx 45 GeV is confirmed.