Does exothermic solvation mean solute is more soluble at low temp?
Think of this in terms of equilibrium constant.

$$K=e^{-{\Delta G\over RT}}=e^{-{\Delta H-T\Delta S\over RT}}=e^{-{\Delta H\over RT}}\cdot e^{{\Delta S\over R}}$$

Now it is pretty clear that exothermic reaction means negative $\Delta H$, which in turn means positive coefficient in $-{\Delta H\over RT}$, which consequently is a decreasing function, as is the whole exponential expression. The entropy change (or indeed the sign of it) does not matter.

The example of $\ce{CaCl2}$ is irrelevant, for anhydrous $\ce{CaCl2}$ is never the phase in equilibrium with the solution. Roughly speaking, one simply cannot just up and dissolve $\ce{CaCl2}$. In effect, there would be two reactions: first the hydration, which produces $\ce{CaCl2.6H2O}$ (that's the exothermic part), and then the dissolution of that.

The implicit approximation we relied upon is that our $\Delta H$ and $\Delta S$ won't change much throughout the dissolution process. This fails when it comes to insanely well soluble things (think of $\ce{NaOH},\;\ce{KOH}$) where by the time we reach equilibrium, we might even have more solute than water. Naturally, the properties of such solution would be quite different from those of pure water.