The recent identification of strongly bound excitons in room temperature anatase TiO$_2$ single crystals and nanoparticles underscores the importance of bulk many-body effects in samples used for applications. Here, for the first time, we unravel the interplay between many-body interactions and correlations in highly-excited anatase TiO$_2$ nanoparticles using ultrafast two-dimensional deep-ultraviolet spectroscopy. With this approach, under non-resonant excitation, we disentangle the optical nonlinearities contributing to the bleach of the lowest direct exciton peak. This allows us to clock the ultrafast timescale of the hot electron thermalization in the conduction band with unprecedented temporal resolution, which we determine to be < 50 fs, due to the strong electron-phonon coupling in the material. Our findings call for the design of alternative resonant excitation schemes in photonics and nanotechnology.