Perhaps you have a failing wire from the sensor to the board. For some reason, it seems to be a common issue affecting the "sense" wire (but not the power wires) in the cable supplied with the probe.
When a copper wire is bent back and forth at a single point, it will eventually break (called a "fatigue failure"). The insulation around the wire will be intact, so the failure is not visible. After the wire has broken, then in certain positions and in certain conditions it can still conduct electricity - if the two ends of the wire are touching each other. But if the ends of the wire get pulled apart (even by microns) then there's no conduction.
So look for a place in the wiring harness where the wire gets bent back and forth "at a point". To verify that there is a fatigue failure there, try manually pushing, pulling, bending the wire while frequently issuing the M119 command. You may need to do this with the probe "close" to metal and again with the probe "far" from metal. The exact conditions to make the failure show up depend on whether an open circuit (broken wire) simulates "triggered" or "open", but from your description it seems that maybe "open" corresponds to the broken-wire condition.
In the long run, you should look at finding ways to spread the bending out so that your wires gently bend over a large distance rather than bending "at a point". Cable Chain is one way to do this (several posts about it are in this forum; don't get hung up on the early discussion about the philosophy of how to do cable chain best. For you, it doesn't matter if you get 100 million cycles or 10 million cycles; your failure is coming after 10000 cycles!).
Printrbot Plus operational January 2013
Brass threaded rods (5/16" X 18) & nuts for Z axis
GT2 belts & pulleys
Cable chain to reduce probability of fatigue failure in wires
E3D V5 Hot End, 0.4mm nozzle, also 0.8 and 0.25 in use occasionally
PB fan mount + 40mm fan -- using printed mount adapter, not the E3D supplied fan
Injection molded extruder gears
Optical Z "endstop" (custom designed and built)
Have used many pounds of T-Glase filament. Now also doing some work with Ninjaflex SemiFlex
Print on glass with Scotch Craft Stick or other glue stick