For over three decades, the giant elliptical galaxy Messier 87 in the Virgo Cluster has hosted the most massive known black hole in the local universe. New observational data and improved stellar orbit models in the past several years have substantially expanded and revised dynamical measurements of black hole masses at the centers of nearby galaxies. I will describe recent progress in discovering black holes up to twenty billion solar masses in ongoing surveys of massive elliptical galaxies. This new population of ultra-massive black holes is revising our understanding of the symbiotic relationship between black holes and galaxies, and of the gravitational wave signals from merging binaries targeted by ongoing pulsar timing array experiments.