We calculate O(alpha_s) two-loop virtual corrections to the differential decay width dGamma(B --> X_s l^+ l^-)/ds, where s is the invariant mass squared of the lepton pair. We also include those contributions from gluon bremsstrahlung which are needed to cancel infrared and collinear singularities present in the virtual corrections. Our calculation is restricted to the range 0.05 < s/m_b^2 < 0.25 where the effects from resonances are small. The new contributions drastically reduce the renormalization scale dependence of existing results for dGamma(B --> X_s l^+ l^-)/ds. For the corresponding branching ratio (restricted to the above s-range) the renormalization scale uncertainty gets reduced from +/- 13% to +/- 6.5%.