What was removed, or planned but never made? I don't mean the radiant AI. I mean full on story, locations etc. I heard there was a town NW of Kvatch that was removed. What else?

go read the wiki? -from my googling efforts - nothing

There was to be another town - Sutch. It was at the present location of Fort Sutch.

Weapons, quests, items. As far as game mechanics, most likely not much. The Radiant AI being reduced down to a fraction of its former self was the most noticeable and may have allowed them to keep many of their other creations intact. You have to remember they had to switch from creating a game with the Xbox in mind to creating a game for the next generation of platforms. So most of their efforts probably went into that overhaul. Besides I think they covered enough ground here that the cut things may have allowed for an on time release and a much more stable game.

It is believed there was to be a questline involving the Elder Council and rebuilding Kvatch, but the idea was scrapped and the only evidence left was the Signet Ring carried by Count Ormellius Goldwine.

There is a dialogue topic you get early on in the game: "Do you need couriers?" that apart from the message of it being added, is never referenced again and can never be discussed. This might signify a quest (or series of) involving the Black Horse Courier might have been in development early on, but it got cut from the game.

Thank goodness for mods which add in all three of these things

Supposedly there is a flattened area in the geography near Fort Sutch that was where the town of Sutch would have been.

Did some digging and found some interesting tidbits on Sutch.

Some in game journal references mention Sutch according to info on the bottom of http://www.uesp.net/wiki/Oblivion:Azzan on UESP Wiki.
Uesp Wiki page on http://www.uesp.net/wiki/Oblivion:Brina_Cross_Inn mentions Sutch in the notes toward the bottom of the page. Plus a map on that page showing Sutch, in the lower right corner.
Interesting post at the top of the http://www.thenexusforums.com/index.php?/topic/207504-new-version-of-sutch/page__st__10 mentioning briefly of an Oblivion map that included Sutch on it, and apparently still found in some actual, minute content on the game disc.
Not sure if this http://www.youtube.com/watch?v=IoCJ2y3X3Z4 is a demo video of a town of Sutch mod, but it seems to be showing some features of the game, like grabbing objects, that I don't think the modder would include in their demo if indeed it is a trailer video for a mod remaking Sutch.

Every town was meant to have an Arena, but they cut it down to just one big Arena in the Imperial City.