OVH was pestering me about migrating my VPS from its previous range to the new (and more expensive) one. I finally agreed to that. Migrated the VM to the new host, it launches with no networking. Not entirely unexpected, but it gets better.
The root cause is the DHCP server at OVH returning a lease with netmask /32. In that situation, it's not possible to add a default route, because the next hop is outside of the netmask.
Seems like a simple enough problem, so I filed a ticket in OVH support, basically saying "your DHCP server supplies incorrect netmask, please fix it." Their ultimate answer was, and I quote:
Please note that the VPS IP and our failover IPs are a static IPs, configuring the DHCP server may cause a network issues.
I suppose I knew what I was buying when I saw the price for these OVH VMs. It was too cheap to be true. Still, disappointing.