I've realized that, as bug reports go, my first post missed some detail... So
I've run some more tests with versions 3.33 and 3.40, and they display a
different behaviour. 
7-Zip refuses to open the *.zip cache files, claiming they are "not supported
archive", so in order to check the cache status I grepped them searching for a
specific entry related to a deleted file.

Test platform is Windows 2000 SP4 + IE 6 SP1. Here's what I have done (taking
a snapshot of the mirrored site after each step) and the results:

1) Mirrored a smallish (7 MB) site. Options used: '--path', '--proxy',
'--index'. Deleted some files (case in point, all those starting with 's').

2) Updated the mirrors ('-i') specifying only the option  '--do-not-recatch'
(the others were retrieved from cache).
Result: both versions created zero length files in place of those deleted.
Entries for the erased files remote URLs were present in 'old.zip', but not in
'new.zip'.

3-A) Deleted bogus 0-byte files (as I would normally do in a production
environment) and launched a second update, again with said options.
Result: both versions redownloaded the files. Cache entries (only in
'new.zip') for erased files were only present in v. 3.40.

3-B) Restored both folders from snapshot. Re-updated the mirrors, this time
keeping the zero length files.
Result: version 3.33 kept the bogus empty files, v. 3.40 redownloaded them
from scratch. Cache entries (only in 'new.zip') were present with both
versions.

Hope this helps track down the problem...