After some debugging, turns out the root problem is that get_custom_logo() first retrives the logo ID by retrieving get_theme_mod( 'custom_logo' ). That option is set when setting a site logo but it's noc cleared when the image is deleted from the Media Library (or deleted from the file system).
get_custom_logo() does check if the$custom_logo_id exists but that comes from the site_logo option in the wp_options table. That value still exists even when the referenced image is deleted from the Media Library.
get_custom_logo() does _not_ check whether the image actually exists. When the image is deleted from the Media Library, wp_get_attachment_image returns an empty string and there's no check for that, the markup is rendered regardless and prints an empty string.
Looks like this function assumes the image does exist when the custom_logo/site_logo option is set, which isn't true.