What color are the LEDs? I am interested in the forward voltage drop and the size of your current limiting resister. If the things are red, the forward drop is close to the PIV. Don’t take this wrong but, is it possible that you have the polarity wrong?
If everything else is as you say, then that, thermal damage from soldering and high frequency voltage spikes from somewhere are the only reasons I can think of that would cause the type of failure you describe. Short strings with its own resister from a 12v. to 14v. supply should work fine. If your power source has a battery charger attached, bypass the input with both a large electrolytic and a small ceramic cap just to make sure that any voltage spikes never get to the diodes.
I agree about the waste of power in a resister if it is not selected properly. Therefore, the voltage drop across the resister should be as low as possible. Example, if the forward drop of the LED is 2 volts, then each string should be 5 LEDs. If you use a 600 ohm resister, that would provide a forward current of 20ma @ 12 volts 23ma @ 14 volts and about 1/3 watt of power loss per string. Increasing the voltage and the number of LEDs in the string will reduce the total power loss in the resister if regulation can be maintained so it is still dropping only 2 to 4 volts. That means as you double the supply voltage you have to halve the regulation tolerance to save anything. I wonder, is it actually worth it in the long run?