No sé si se podría decir que "encontré una solución"... más bien me advirtieron de una falla. Y la comparto acá por si a alguien en algún momento le sirve. Es para darle una alternativa más a quien esté en la misma situación.
Después de probar todas las alternativas que leí en distintos lados, ya me había dado por vencido con buscar una solución por software. Entonces, volví a revisar los registros (seguía pensando que era un problema con la configuración, o algo semejante).
El problema estaba en la configuración del puerto B. A cada pin del puerto B se le pueden habilitar las resistencias pull-up internas. Esto se hace con el bit 7 del registro OPTION_REG. Lo había puesto en 0 en lugar de en 1.
bit 7 RBPU: PORTB Pull-up Enable bit
1 = PORTB pull-ups are disabled
0 = PORTB pull-ups are enabled by individual port latch values
Luego, en mi protoboard, ponía todas las entradas que no utilizaba (para ir testeándolo de a partes) a masa. Con lo cual, lo que termino pensando que pasó (esto sumado a una realización bastante floja del protoboard, que después tuve que revisar y 'robustecer') es que quemé el puerto B completo.
O por lo menos, se jodieron los pines RB6 y RB7, que casualmente son los usados para programar.
No estoy 100% seguro que haya sido eso. El PIC no se calentó, ni dio señal alguna. Simplemente perdió toda conexión, y ya no fue posible leerlo, ni escribirlo. Aunque el software si lo reconocía como un 16F876A.
Desde que modifiqué el registro OPTION_REG, (y acomodé un poco las conexiones falso-contacteras del protoboard), ya grabé/borré/leí unas 40 veces el nuevo PIC.

Como dije antes, dejo esto sólo como una opción más a tener en cuenta. Veo que la imposibilidad de borrado/grabación de pics es un tema recurrente en muchos foros, y en gran parte de los threads no llegan a una solución.
Gracias por los comentarios, MGLSOFT y AngelGris, y a los que se tomaron un rato para leerlo.
P.D: MGLSOFT, ¿cuál superpoderoso me recomendarías que salga la mitad que este?
Saludos!
Martín