I finally solved it.

I found this very useful snippet in the PICkit2's User's Guide:

Use VPP First Program Entry - When checked, it allows the PICkit 2 to connect to and program devices with configurations and code that interferes with the ICSP signal pins, preventing PICkit 2 from detecting them.
Once I set that, they erased like a dream. So three 18F1320's saved from the trash