Ico's horns, at first, used to point downwards. They were changed late in the development cycle because Ico seemed inadvertently submissive that way.
Yorda went through a myriad of changes. In the pilot movie she wore a horned helmet and cursed runes on her right arm. The runes were intended to function as a health indicator. Her clothes and hair were constantly being modified. Ueda-san even gave her 'a haircut' the day before the final version of the game was due.
The smokemen we see in the final version of the game weren't the first type of enemy. In the pilot movie they were robots and when development started they were turned into soldiers. In a later build of the game, after the enemies were changed yet again, there was a segment, before the end sequence with the Queen, where the player faced a large number of smokemen of gigantic proportions. The idea was abandoned because it required considerable additions to the fighting system.
Many of the things that were modified appeared again years later in Shadow of the Colossus (the huge enemy) and The Last Guardian (the cursed runes, the soldiers).