You may want to look for the Crysis 2 Multiplayer Demo.
It has such killcams where you can even see the bullet.
Basically I would do it the way lemming suggests:
Record the match on the client but make sure you
also simultaneously delete all the data older than
the 5 seconds - it may be too much to handle. Depends on the
amount of used data in the game I guess.