Motivated by the recent detection by WMAP of a large optical depth to Thomson scattering -- implying a very early reionization epoch -- we assess a scenario where the universe was reionized by `miniquasars' powered by intermediate-mass black holes (IMBHs), the remnants of the first generation of massive stars. Pregalactic IMBHs form within minihalos above the cosmological Jeans mass collapsing at z=24, get incorporated through mergers into larger and larger systems, sink to the center owing to dynamical friction, and accrete cold material. The merger history of dark halos and associated IMBHs is followed by Monte Carlo realizations of the merger hierarchy in a LCDM cosmology. While seed IMBHs that are as rare as the 3.5-sigma peaks of the primordial density field evolve largely in isolation, a significant number of black hole binary systems will form if IMBHs populate the more numerous 3-sigma peaks instead. In the case of rapid binary coalescence a fraction of IMBHs will be displaced from galaxy centers and ejected into the IGM by the `gravitational rocket' effect, rather than accrete and shine as miniquasars. We show that, under a number of plausible assumptions for the amount of gas accreted onto IMBHs and their emission spectrum, miniquasars powered by IMBHs may be responsible for cosmological reionization at z~15. Reionization by miniquasars with a hard spectrum may be more `economical' than stellar reionization, as soft X-rays escape more easily from the dense sites of star formation and travel further than EUV radiation. Energetic photons will make the diffuse IGM warm and weakly ionized prior to the epoch of reionization breakthrough, set an entropy floor, and reduce gas clumping. Future 21 cm observations may detect a preheated, weakly-ionized IGM in emission against the CMB. (abridged)

12 pages, 8 figures, revised version accepted for publication in the Astrophysical Journal