Going by the description of the failure and the datasheet, I'm going to guess that the output of the regulator is oscillating.
The datasheet specifies particular characteristics of the output capacitor, and mentions that they are required for stability - that is, to prevent oscillation.
Minimum capacitance 22uF.
The equivalent series resistance (ESR) of the capacitor. The chart says 3 ohms, but there's a diagram showing the relationship between load and the ESR needed for stability. You should have no more than 3 ohms, but if your circuit draws more (or less) than around 150mA you can get away with more.
You have more than enough capacitance, so I expect the problem lies in the ESR.
You mention supplying 12V at 0.02A to the whole circuit. That implies that the 3.3V load is very small, in which case you could get away with a capacitor with a higher ESR
This diagram from the datasheet shows the relationship between load current and required ESR of the output capacitor:
At around 150mA of load current, you may have at most 3 ohms of ESR. If your load is very low or very high, you may get away with up to 10 ohms of ESR.
If your regulator works correctly with one load, but burns out with another, then I'd compare the stability curve and the load currents for the two loads with the ESR of the output capacitor.
You can increase the ESR of your output capacitor by adding a small resistor in series, but the only way to reduce ESR is to use a different type of capacitor.
You mention electrolytics, and from the footprint shape I'd assume you are using aluminum electrolytic capacitors. You may need to switch to special low ESR aluminum capacitors or ceramic capacitors.
If you go with ceramic, remember to consider derating - you will need to use a higher rated capacitor (more than 22uF) because ceramic capacitors lose capacitance when voltage is applied. Whether it is a problem or not depends on the rated voltage of the capacitor. A 50V capacitor won't lose much capacitance at 3.3V. A 5V capacitor may lose a significant portion of its capacitance at 3.3V.
The description of the problem sounds very much like the regulator is oscillating. They tend to get hot when they oscillate, and your multimeter can't really follow the oscillating voltage and so it displays a varying voltage. They also draw a lot of current when oscillating.
Oscillate, draw a lot of current, get hot, burn out.
If you have an oscilloscope (and a spare regulator or two,) you could check the output of the regulator and see it oscillating. By the time you get done looking, though, the regulator will probably be toast.
I have killed my share of regulators by neglecting the ESR requirements. That's why I think you are experiencing this particular problem - I've had it happen, and it matches your description.
Thing is, when I encounter a misbehaving circuit, I reach for the scope first rather than the meter. I saw it oscillating before I knew the output voltage was wrong.