Hola
Stray´s Phone, lo que puedes hacer es pedir permiso al dueño de los derechos.
También te puedes centrar en la música con anuncios que encontrarás en
https://www.youtube.com/audiolibrary/ad_supported_music. Pero debes tener en cuenta que los propietarios de los derechos de autor de esas canciones pueden cambiar sus políticas en cualquier momento o tomar otras medidas con respecto a tu vídeo (distintas a las que te comentan ahí) y sufrir en el futuro lo que te está ocurriendo ahora.
¿Has oído hablar de la música publicada bajo licencia
Creative Commons? Sus creadores permiten que otras personas utilicen sus obras...
¡Saludos!