New table or new column
I'd go with option 3, which will require less overall work:


Make a lookup table that contains a list of purged records and dates, like in your first option
Rename your current table to something like dbo.Tablename_master
Create a VIEW named dbo.Tablename which consists of:


.  

SELECT &lt;fields&gt;
FROM dbo.Tablename_Master
WHERE PrimaryKeyField NOT IN (SELECT PrimaryKeyField FROM PurgeTable)


Now you don't need to modify any existing code, since all references to your original table go through the view instead.  This will be complicated if you have any existing constraints but they should be easy to work around.