If you happen to have any more details about specific stories that reappeared, I’d love to try and figure out exactly what happened. Admittedly, that may be difficult now that several months have passed.
As one of the other commenters mentioned, your Activity Log is a better place to get a full list of your activity and delete it item-by-item. It also shows posts that Timeline omits and includes other types of content such as likes and comments. This help page may be useful https://www.facebook.com/help/activitylog and you can find your Activity Log at https://www.facebook.com/me/allactivity?privacy_source=activ...
I couldn’t tell from your description, but one possibility is that you only saw and deleted the stories rendered on your Timeline, which is just a summary of your activity.