PC games with a record replay feature:

[Sid]

You can add also "Ghost Recon" - it has replay function, which allows to record and watch whole missions - the only problem is, that it's a little bugged - sometimes it doesn't save enough data about player aiming (so while watching replay crosshair can be away from enemy soldier but he'll die - it just looks kinda strange).

Anyway, if Ghost Recon have this function, so it's expansion packs should have it also:
- Ghost Recon: Desert Siege
- Ghost Recon: Island Thunder

Oh... "IL-2 Sturmovik" has demo recording feature also.

[Ewil]

Just noticed a mistake: Doom 3 is id tech 4, not 5. id tech 5 will be used for Rage and Doom 4

[guestoieahjt]

Rise of the Triad anyone?

[Inexistence]

Harry Potter and the Chamber of Secrets doesn't have it. I enabled debug mode, which let me get a console, but trying to record anything would cause a crash no matter what I tried.

[Pendrokar]

Then probably both don't have it.

[Red_Shifter]

Tribes: Vengeance has demo recording.  According to a site I read, you need to use demorec <demoname> in the console to record and use demoplay <demoname> to replay it.  The console is activated by specifying a -console switch on your shortcut.  The game is very glitchy, and I've heard demo recording in the game has a major performance hit.  I'm not even sure if you can record single player.  I'm not reinstalling that cheap imitation of a Tribes game to find out.