What type of design logic have you implemented in the CPLD?
Back before I knew better, I created a design that used a latch, rather than a register. I placed-and-routed the design with Mentor LeonardoSpectrum and then WYSIWYG compiled the EDIF netlist with MAX+Plus II. I downloaded the design into a FLEX10K, and very soon after I could smell something cooking ... the FLEX10K device!
I ran the post-P&R design in Modelsim to try and determine the problem. Modelsim showed an oscillation of a signal associated with the latch. The placement of the latch was such that there were different delays in the latch feedback paths. Those delays created an oscillator at several hundred MHz (actually several oscillators, since the latch was multi-bits). This was enough to cook the chip.
If you are seeing a random issue across boards, then perhaps you have something that is design related, and the slight differences in device timings causes the problem to occur on only some boards.
Replace the device on a bad board with a blank CPLD. If that CPLD does not destroy itself after the board has been powered up for longer than it took for the first CPLD to be destroyed, then I would look at the design, eg. simulate the post-P&R design.
Cheers,
Dave