Several good points here. I agree with Aussie_Lurker's idea 1 and 2. As Horus Kol wrote, forts must cost something to avoid abuse. Maybe requiring a resource as stone, a technology (masonry or construction) and several turns to finish. Also, colonies aren't useful because they don't create any border. Anyone can send a settler near and get that resource. Maybe colonies could create a small border (1 square) after 10 turns and become cities after 20 turns. What do you think?
I don't think that claiming territories would work. It can work well with human players, but it's hard to make AIs use it well. Several civs will claim the same amount of land, even in "undiscovered" areas. So, there will be a lot of war quickly and most civs will stay weak.
All previews about Civ4 are saying that AI will respect your borders and won't pass it until a RoP or something like it. So, if you have a lot of land and an AI is in a restricted area, without any place to go, it will possibly do 2 things: research a technology to get ships quickly or create a huge amount of units, preparing for war to get a "passage".