There's no YouTube to MP4 tool for deleted videos. Viewing videos requires a signature generated by Google which can only be retrieved if you can access said video. Your best bet other than contacting Google would be the Wayback Machine, but I doubt it would be saved since it was age-restricted.
Could you send over a link to the video so I can check for certain?
I already checked Internet Archive and the video was apparently archived a year after its deletion. When you go to the snapshot it never loads.
The video may have been downloaded by a few users before its deletion.
Yeah, that's your best bet at this point. Just to be sure, I ran it through a program I wrote that checks for stray video downloads and there's nothing there either.
There's still the chance that Google could send you the video, but that's unprecedented AFAIK. Not to mention how we don't even know for certain that what they have about the video includes the video itself.