How should deletions be handled in the database?
Yeah, I would definitely go for the second option, but I would add one more field a date field.

So you add :

delete       boolean
delete_date  timestamp


It would let you give a time for the undelete action.

If time is less than an hour one can undelete.

To really delete the entry deleted just create a stored procedure that will clean every entry with delete set to true and time greater than one hour and put it as a cron tab that runs every 24hours

The hour is just an example.