Not able to program Attiny85-20PU
I found the problem!

After giving high voltage erasure of the fuses a desperate trial - to no avail - it came to me that the problem might be SPI clock speed.

And indeed, when I changed the SPI clock speed inside the ArduinoISP sketch (excerpt below) from my previously tweaked value of 1 Mhz to the value recommended for Attiny85, programming (as well as device signature recognition) worked again!

// Configure SPI clock (in Hz).
// E.g. for an attiny @128 kHz: the datasheet states that both the high
// and low spi clock pulse must be &gt; 2 cpu cycles, so take 3 cycles i.e.
// divide target f_cpu by 6:
//     #define SPI_CLOCK            (128000/6)
//
// A clock slow enough for an attiny85 @ 1MHz, is a reasonable default:

// Working with Attiny85 (the default in the ArduinoISP sketch):
#define SPI_CLOCK       (1000000/6)

// I tweaked this in the past, but it's not working with Attiny85:
//#define SPI_CLOCK 1000000UL 

#define USE_HARDWARE_SPI


I did not notice that although Attiny85 is set to 8MHz default internal clock speed, there is also a clock divider of 8 active by default, so CPU clock is actually at 1 Mhz.