We had a really wierd freezing problem a while back, it was a bear to diagnose, but wasn't to bad to fix once I finally figured out what was going on. It is relevant because I've seen more than a few houses set up this way, and it shows the subtleties of insulation problems.
Our laundry room is a long narrow room between the house and the garage. It is heated (HVAC), but at the end of a run and tends to be on the cool side. Occasionally after running a load of wash, we would come out and find the carpet soaked around the washer. I would then run test cycles, w/o problems, check the hoses and so forth and not find any issues, and generally not find anything at all wrong. The amount of water involved didn't seem to be that large, as it soaked the rug around the machine, but not the entire room, and there were no puddles, etc.
Eventually I figured that it had to be a problem on the drain side, as the wall was wet in that area, but there was no sign of moisture around the supply lines. It turns out that the drain is in a wall that is one side of the recessed front entrance, putting it in an outside wall. The drain pipe is in a slot cut in the sheetrock and recessed a bit into the insulation, but I didn't think of it as a big problem since it should be mostly empty. However I found ICE in the insulation when poking around after one of the flooding incidents. It appears that the pipe got closer into the wall the further down it went, until it was just about up against the outside wall at the trap level.
As best I can tell, the water in the trap was partially freezing, not enough to damage anything, or even to totally block the drain, but just enough to cause it to backup and overflow. The water that was making it through apparently would then melt enough of the ice away that when I would come along and do a test cycle a while later, everything would work fine!
My solution was two parts, first I tried to stuff as much insulation between the pipe and the outside wall as I could, while leaving it exposed on the inside. Then I found a short electric pipe wrap (IIRC it was about 3' and 20 Watts) with an integral thermal sensor to turn it on. I wrapped the trap area only with it, and plugged it in. Haven't had the problem since.
Otherwise, our basement is partly finished, and seems to stay in the 50's in the winter, even with the furnace not on. We have gas hot water, and the pipes do run around the basement some, but not a huge amount, and mostly not against the outside walls. There is probably about 3' average exposure of the concrete basement walls above ground.
Gooserider