Well, from my knowledge of TEC's and the peltier effect, there is an optimum temperature for the hot side of the TEC. It depends on what kind of TEC your using.
For the kinds of TEC's used in cooling computer systems, you achieve the greatest delta-T when the water is ABOVE freezing. There are a few reasons for that, one of them was mentioned. Ice crystals can form, even with antifreez, and that hampers water flow. Second, the effecience of the TEC decreases as the hot side temperature drops.
I've found, and even read elsewhere, that you achieve optimal delta-T and efficiency when the hot side of the TEC is 10-15 degrees below ambient, but above freezing. With ICE-71 peltiers (71 degree DeltaT, 13.4 volt, 8amp TEC), I try to sustain a 10-12 degree hot side temperature, and my cold-side easily sustains -20 under a full, sustained cpu load. It drops close to -52 when the system is completely idle.
I'm not achieving a 71 degree deltaT, its more like 60 degrees, which is expected. Its impossible to achieve perfect operation in a real-world situation.
Also, some other tips. Optimal TEC operation depends more on voltage than hot side temperature. For most high-efficiency TEC's, you need at least 13 volts for them to operate efficiently. Supplying less voltage quickly reduces efficiency. My ICE-71's, for example, operate quite poorly at 12 volts (I can hardly sustain sub-zero temperatures under load, and my lowest was -12 idle). Providing too much voltage can have a detrimental effect as well, lowering efficiency while producing too much heat. TEC's like to have stable current and voltage, and they have a very short "sweet spot" where their effeciency is optimal.
Hope this helps. Most of this comes from experience, but I learned a lot just by searching the web for information, much of which I found either from links here on ProCooling or on Overclockers.com.