The only way to turn the MOSFET off is to raise the gate voltage to meet the source voltage, in other words 12V. You confirmed what I suspected, any voltage lower than about 8V would turn the MOSFET on and the PIC is only capable of going up to 5V so it is impossible to it to turn the MOSFET off.
You have two solutions, one is to replace the MOSFETS with N-Chanel types so the PIC and source pins can both be grounded or, you can add transistor driver stages between the PIC and MOSFET. The transistor driver is probably the easiest solution, just wire NPN signal transistors with emitter grounded, base to the PIC via 1K resistor and collector to 12V through a 470 Ohm resistor. The gate of the MOSFET goes to the transistor collector. Now the PIC can drive the NPN transistor hard on and off and it's collector will go from 12V down to near zero so the MOSFET gets the drive voltage it needs.
You should note that adding the transistors will invert the PIC signals (PIC pin = 0 means the MOSFET conducts) but as the drive is symetrical anyway it shouldn't make any difference in this design.
Brian.