one of the best freeplay story development i have experienced so far was in epic2.
a simple spaceshoter game but with one remarkable option: the mission tree.
whenever you fail a mission (escorting some cargo ships aso) it didnt lead to a replay of the mission but the story simply continued. If you where not able to stop a weapon transport of the enemy, you still could continue but had to face another level.
after you have failed about 3-4 missions in a row (depending) you where game overed by "imprisoning".
this game had the hell of a motivation factor. first of all it played like battle star galactica and you where allowed to fail missions and the whole story and further mission desing reacted to it.
i have seen aspects of this in other games as well but never in such a great layout ever again.
deusx was not really that unlinear, but it offered you to solve missions in a few different ways. other games do this as well (thief for example).
deusx though had one big problem: you could get lost during the game. Not knowing what to do is very bad ingame.
But all of those games have a big replay motivation factor. somthing i am missing in games today.
cheers