Meanwhile, I managed to solve this problem.
The reason for the verification error is that the two most significant bits of the Lock Byte are read-only on my variant of the Arduino Pro Micro. Which means that, if you (try to) write a value of 0x00 = 0b0000 0000, it will result in a value of 0b1100 0000 = 0xC0 on the hardware.
The solution, then, was to simply ...
If you're using Nick Gammon's programmer, the RESET signal to the target board comes from the Arduino programmer - from Pin 10. Read his instructions:
You modify the 6 pin cable as shown on his website.