Are there materials that get softer with temperature decrease? Could be there material that begins melting/softening when it's temperature is lowered?
I would say no, but I've seen enough physics to know that not always life is so easy.
Moreover I think I've heard something about it, but can't remember a thing.
 A: Materials that exhibit entropic elasticity will theoretically exhibit this effect. For example, elastomers that at a temperature far greater than the glass transition temperature.
In entropic elasticity, stiffness arises not from stretching mechanical bonds, but by decreasing the entropy of the polymer chains in the material. A derivation of this phenomenon is beyond the scope of this question, but here's the punchline:
The initial shear modulus of the material is proportional to the absolute temperature. This fits the bill for a material that "softens when it gets colder." 
Here is a link to the Wikipedia page for rubber elasticity. This phenomenon is described in more detail here.
http://en.wikipedia.org/wiki/Rubber_elasticity
A: You may wish to google "retrograde melting" - some allows/mixtures do melt with cooling. See, e.g., http://xraysweb.lbl.gov/uxas/Publicatons/Papers/pdfs/hudelson%20adv%20mat.pdf
A: There's a nitinol wire that stiffens when warm and softens when cool.
It's been used in various patented heat engine applications. see this reference http://www.imagesco.com/articles/nitinol/09.html
