The separation of one compound from another by crystallization hinges on the difference in solubility of the two compounds at two different temperatures. While it might be more difficult to separate something that decreases solubility at higher temperatures, I wouldn't think that, per se, would make it impossible to do if the solubilities of the two compounds were sufficiently different. However, rather than get into a dither about it, I would change solvents and use recrystallization the regular way.
How is possible though--to have a substance whose solubility decreases as the temperature increases?
Na2SO4 (anhydrous sodium sulfate) is a material that decreases its solubility as T increases. It is an exothermic process.
Na2SO4*10H2O + heat ==> Na2SO4 + 10 H2O
According to Le Chatelier's Principle, adding heat causes the reaction to proceed from left to right more, decreasing T causes the reaction to move to the left. Anhydrous Na2SO4 decreases its solubility from about 60 g/100 g H2O to about 45 g/100 g H2O as T is changed from 30 C to 100 C. Solubility is due to a host of things that range from hydration energy of the ions (solvation), energy needed to break the crystal lattice, energy needed to break the hydrogen bonds of water molecules(if that is the solvent), etc. Whether the process is exothermic or endothermic depends upon the individual factors above. MOST salts are endothermic when they go into solution; therefore, their solubility increases with increasing T. However, for those salts that are exothermic, the reverse is true.