I did some more testing, using Windows there's a problem if
you want to keep the pathname.
I extracted a "new.zip" folder by folder with 7-Zip (option
Path mode / no pathnames) and ICEOWS (extract with path
unticked).
I also deleted a few files but I couldn't reproduce your
problems.

I had no problem at all to unzip and keep pathnames with
Linux. Maybe you could try.
 
I hope there's a solution if you need to use new.zip (I use
the mirror instead)