Our database is Microsoft SQL Server 2000.
Turns out the record wasn't to be deleted anyway. So I get yesterday's backup of the database, and go to insert the deleted rows. I got an error saying that I can't insert into an identity column.
In order to properly restore the database, I needed to restore the ID. After some searching, I found the solution.
Assuming that you are restoring a record to the foo table, the following fixes the problem
SET IDENTITY_INSERT dbo.foo ON
INSERT dbo.foo
(ID, Occurred, [Status])
Values (1234,'2011-08-09 09:27:51.383','new');
SET IDENTITY_INSERT dbo.foo OFF