Many promising optoelectronic devices, such as broadband photodetectors, nonlinear frequency converters, and building blocks for data communication systems, exploit photoexcited charge carriers in graphene. For these systems, it is essential to understand the relaxation dynamics after photoexcitation. These dynamics contain a sub-100 femtosecond thermalization phase, which occurs through carrier-carrier scattering and leads to a carrier distribution with an elevated temperature. This is followed by a picosecond cooling phase, where different phonon systems play a role: graphene acoustic and optical phonons, and substrate phonons. Here, we address the cooling pathway of two technologically relevant systems, both consisting of high-quality graphene with a mobility >10,000 cm2V1s1 and environments that do not efficiently take up electronic heat from graphene: WSe2-encapsulated graphene and suspended graphene. We study the cooling dynamics using ultrafast pump-probe spectroscopy at room temperature. Cooling via disorder-assisted acoustic phonon scattering and out-of-plane heat transfer to substrate phonons is relatively inefficient in these systems, suggesting a cooling time of tens of picoseconds. However, we observe much faster cooling, on a timescale of a few picoseconds. We attribute this to an intrinsic cooling mechanism, where carriers in the high-energy tail of the hot-carrier distribution emit optical phonons. This creates a permanent heat sink, as carriers efficiently re-thermalize. We develop a macroscopic model that explains the observed dynamics, where cooling is eventually limited by optical-to-acoustic phonon coupling. These fundamental insights will guide the development of graphene-based optoelectronic devices.