I just checked my DVD, and the scene you referred to is in it. It was also in the pre-'97 VHS videotape of the theatrical release of Part I. I agree that, if the Don/Fredo/Genco scene had been deleted, Sonny's selection of Paulie as the traitor would have lacked justification. But the Don/Fredo/Genco scene nicely points the finger at Paulie.

Ntra la porta tua lu sangu � sparsu,
E nun me mporta si ce muoru accisu...
E s'iddu muoru e vaju mparadisu
Si nun ce truovo a ttia, mancu ce trasu.