Does exothermic solvation mean solute is more soluble at low temp? (I'm surprised this question or a very similar one hasn't been asked, so I wouldn't be surprised if I just failed to find a question with my search that does answer this question.)

I dissolved some $\ce{K3PO4}$ in water a while back, and the solution became very hot. I commented on this to my labmate, and he said "So that means it's more soluble at low temperature, right?" I evaded response because I disagreed but didn't have a thought-out response yet.

I think he thought of the reaction as:
$$\ce{K3PO4 -&gt; 3K^+ + PO4^{3-} + heat}$$

But I think that's missing an important step. I think it's more like this:
$$\ce{K3PO4 -&gt; 3K^+ + PO4^{3-}}$$
$$\ce{PO4^{3-} + H2O &lt;=&gt; HPO4 + OH- + heat}$$

Phosphoric acid's third pKa is pretty high, so the second reaction is pretty significant. This, I would say, is why this particular reaction is so exothermic. So, in this case, I don't really think the heat plays into the solubility of potassium phosphate.

Sometimes, though, solvation comes with a positive change in temperature. For instance, the enthalpy of solvation of sodium iodide is $\mathrm{-7.53\ kJ/mol}$. Sodium iodide, though, is still more soluble at high temperatures. I could be missing something here, though.

In the cases where it is specifically the solvation reaction that causes a temperature change, is it the true that lower temperatures always increase solubility of salts with exothermic solvation reactions (and vice-versa)?

I'd say that the answer is no because the solvation should be dependent on $\Delta H - T\Delta S$ and, since the enthalpy change half of that formula is temperature independent, as $T$ goes up, solvation should be favored by any solvation that has a positive change in entropy. However, I can't really think of any solvation that has a negative change in entropy.
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.