Like Scarab said, the computer's walling algorithm leaves something to be desired. Essentially, it places wall sections pretty much at random within a few squares of a variable called "MaximumTownSize" and above "MinimumTownSize", as memory serves. The only real effective way to get him to wall is in scenarios, and in those cases, you limit his town size to exactly where you want the wall sections placed and put cliffs, water or other terrain features in to make it appear as if he walled intelligently.
I seem to remember something on the ShaiTan site about AI and walling, but it may not be available anymore.
Suffice it to say that in Random Map, the computer cannot be forced to build effective walls.
Keep your stick on the ice.