Prey

ArsTechnica:
Prey has been stuck in development hell for longer than I can remember. You can easily find the trailer for the game that was shown off at E3.
In 1998.

I saw a really early engine demo of Prey in 1997 when I went to the first QuakeCon. It wasn't some big thing. The guy sitting next to me was a developer on it or something.

Prey's been in development almost as long as Duke Nukem Forever. Except Prey actually shipped...