Interesante hilo, dejo mis aportaciones...
El primer King of Fighters se supone que iba a ser un beat em up a lo Final Fight/Streets of Rage con personajes de Fatal Fury y Art of Fighting, esta idea se desecho para dar con el juego que todos conocemos.
El primer Sonic llevaba de titulo Project Needlemouse.
Sony le había mostrado el prototipo de la Playstation a Sega, la sede norteamericana vio visto el potencial de dicha maquina y dio el visto bueno pero la sede japonesa no y debido a eso Sony decidió lanzarlo por su cuenta.
Originalmente hubo un Streets of Rage 4 en desarrollo en los 90s por Core Design, pero dado que Sega no quedo satisfecha con los resultados, decidió cancelarlo, dicho juego se convertiría después en Fighting Force.
Originalmente GTA 3 estaba siendo desarrollado para Dreamcast pero debido a la prematura muerte de la consola no se hizo.
En su fase temprana de desarrollo Max Payne 3 iba a estar ambientado en Rusia.
El primer prototipo de Mafia 2 se mostró en el 2004 y se discutió un port para PS2 y Xbox.