Earlier quoted context omitted.
There are reports they reappeared on sold phones as well
So they sold a phone with their iCloud account connected. Which means all of their current emails, photos, contacts, bookmarks, browsing history, location etc was also available.
My instinct is also to assume they didn't reset their phone, but I also assumed Apple deleted their photos when they deleted them years ago.
I wouldn't be shocked to find it there's some technical cruft around it being a built in mandatory app, and corrupted data was retained.
In fact, when I think about it, if I wasn't biased towards Apple, my prior after a bug involving photo deletion should be to expect bugs involving photo deletion.