Gibt es irgendeine Möglichkeit, von Usern gelöschte YouTube Videos im Netz zu finden?

Unwahrscheinlich. Würde nach Re-Uploads suchen. Oder in der Google-Suche mit Anführungszeichen. "ExAkTeR ViDeOtitEl123"

Manchmal hat man auch Glück, und findet das Video noch in Playlists, wenn es auf nicht gelistet bzw. Linkfreigabe geschaltet und nicht komplett gelöscht wurde.

Insofern es keine Re Uploads gibt nein.

Denke nicht, dafür ist die Funktion ja da.