I think the C84 is pretty old. I can't remember the C71, at all. Anyway, you don't describe what you mean by "couldn't be programmed" very well. I gather you could find it on the programming list, which surprises me a little with MPLAB v5 (I think you may need the archived
5.70.40 version, at least)... as you go on to explain some observations during programming. On OTP parts (somehow, my memory tells me that C parts are OTP, but I might be wrong about the two you mentioned), I recall the need for 13.25V for programming, allowed to drop to something like 12.75V worst case, so the 13V you mentioned sounds about right. Programming time might be a lot less, if you are only programming a few bytes, than verify which may require comparing all of the bytes in the chip memory. I'm not sure about that, though.I'd have to download the programming specification and look at it, though, regarding the clock pins. I'd imagine that if you see activity during blank check, that you'd probably see activity during reading, if not programming. So that is interesting.
Which version of PICSTART do you have? There were some older ones without the modification that allows them to download new code from MPLAB (which is stuffed into its install directories when you install MPLAB.) The newer ones have the programmable chip in them and MPLAB will offer the option to download the newest code into them. And Microchip may still offer the update to modify older ones (it's just a matter of opening the box and replacing a chip with a module they sell, if I recall.)
What I'm worried about is not only support for the C84 in MPLAB, but also support for it in the code on the PICSTART unit. Also, in a case or two that I recall, I had to create an adapter to plug the chip to be programmed into before inserting it into the ZIF on the PICSTART. It's possible that you may have that problem in this case, so I'd recommend looking around (googling?) for that possible problem with the old parts you have.
So, (1) MPLAB should support the part and, I think, should be at least version 5.70.40 (found in archives on Microchip site.) And you must correctly select it, obviously. (2) PICSTART must support the parts in its firmware, as well. And this may mean that you need to update the firmware. (3) Possible adapter may be required.
I'm a bit lazy right now and don't want to read the programming sheets on these parts. Apparently, the C84 is at its END OF LIFE and the C71 is MATURE.
PIC16C84:
PIC16C71:
I've added some of the above links to help anyone else who may want to do a little confirmation of something before writing to you about this. Something that you could have done, but since I took the time I included it here. I've also added comp.arch.embedded to the list, because really that is the newsgroup where you are more likely to find informed responses on this topic.
Jon