We create an ultracold neutral plasma by photoionizing laser-cooled metastable xenon atoms. By changing the frequency and intensity of the ionizing laser pulses, we vary the initial  temperature (1-1000 K) and density (10⁵-10¹⁰ cm^-3) of the resulting plasma.  In the first 100 ms, while the plasma is rapidly expanding, up to 20% of the free charges recombine into Rydberg atoms.  The binding energy released in this process approximately equals the increase in the kinetic energy of the remaining free electrons that was observed in a previous experiment.  Although three-body recombination is expected to dominate in this regime, most of our results are inconsistent with this mechanism.  Liquid-like spatial correlations in our strongly coupled plasmas may render a many-body process more important than conventional three-body recombination.