I would go with the second method.
I don't agree that the second method is difficult. All you need is to create the table. Then whenever someone does a DELETE, you just issue two queries:
INSERT INTO tbl2 (SELECT whatever FROM tbl1 where ...) VALUES(..., ..., ...,) WHERE ...
DELETE FROM tbl1 ...
And u're done!
If you go with the first idea, you'll get a table that is filled with data that may never be used again, and that is surely gonna slow down your queries on that table.
Richie.
geocities.com/akindele/