Hippynerd, you are so on the spot with your last reply, you couldn't have gotten it more right!! Let me explain...
I started playing with the LEDs tonight, to see how much heat they can take. I took a new LED of the very same type (from the batch used for the cube), I set my iron to 370 Celsius degrees (same as I used with the cube), gave the LED current, so that it would be lit up while I heat it to see exactly after how many seconds it goes out and started heating it... and guess what?! after 35 seconds of constant heating near the head of the LED still no sign of burning out. OK, so I tried it on the other leg for another 35 seconds at 370 degrees. Nothing. No damage. I repeated this about 5 times, abusing the poor LED in a barbarian way, but it's still fine, lights perfectly, no damage. I tried it with one more LED, same result. Heat does not seem to burn them out. At least not in 35 seconds. And I only solder them for 3 to 5 seconds, so that cannot be the cause. I was puzzled... So what the hack was burning them out?!
I went to the garbage can and dug out the 4x4x4 cube that I had tossed yesterday night and started de-soldering the LEDs in order to have more to experiment with. At some point I thought I saw one light up while I was melting the solder near it, but there was no current connected to it, so I thought I was hallucinating or something... but no... it happened again and again.
It turns out that when I touch my soldering iron to one leg of the LED and I put my finger on the other leg, the LED lights! It's a bit dim, but you can clearly see it light. And now comes the interesting part: it doesn't matter which leg I touch with the iron and which led I ground with my body. It lights both ways. I guess that the iron is leaking alternative current and that's why it lights. It's getting 50 Hz PWM current, that's why it's dim. So I started playing with it, touching one leg, than the other. After a few touches it went dead. It's burnt. I tried this with another 5-6 LEDs, but they are fine, I did not manage to burn them out, only the first one gave in. I guess some of them are more sensitive than the others...
This perfectly explains why more and more soldering of the cube burns out more and more LEDs. They are exposed to AC for longer and longer times and eventually they burn out. At first I thought that perhaps my wall outlet into which I had plugged the iron does not have proper grounding (the iron does have grounding), so I took it to another outlet in another room. The result is the same. If I touch the LED with it, it ligths (when I also ground the other leg with my finger).
Now the real question is: what is the problem with the iron? And is it just unsafe for the LEDs or is it also unsafe for me to touch? How can I get around this problem? Should I take it back to the store saying that it's not working properly? Or is this something normal? Assuming that this should not happen normally and that it's not just a problem with my iron, but a problem with all the irons of the same type, what kind of soldering iron should I get instead? What detail should I pay attention to?