My best guess is that they were on another device and they are syncing via iCloud and somehow the new iOS fixed a bug that was previously failing to resync photos that were only deleted locally.