I assume you are programming the PLC?

Say you have four inputs... at Power-ON the PIC sets a combination, the PLC looks at this combination, checks it is valid, pulses an I/O to the PIC which then changes the combination, the PLC checks this is also valid, pulses the PIC which now sets a third combination. Finally the PLC verifies this and moves on. If this third combination (which thereafter remains constant) changes, the PLC shuts down. The only way to restart is to Power-On again. So the PIC and PLC exchange three sets of Data at Power-On which have to be valid (you can do this with TWO I/O's and a 'pseudo' Serial chain between the PIC and the PLC).

If the PIC times-out (ie they've not paid their bill), all you do is change the data interchange to something that the PLC will find invalid in the first or second verification.

Another (single I/O) way is to have the PIC perform HPWM Output... say to output a nominal voltage of 4v. The PLC looks to check that the voltage is in the range 3.75-4.25v. If it is outside this range, it can shut-down. All your PIC needs to do is to alter this voltage outside the 'good' band in ordder to shut-down the PLC. To prevent a techie simulating this voltage, at Power-Up, make it go 5v, 0v, 4v in a predetermined time period which the PLC will look for and do a different combination if they've not paid their bill.