Nonsense like a "deleted" column on your main data table just seems silly.
Why silly? Yeah, it's one more column, but most DBs just represent dates as bigints AFAIK so it's not really the end of the world.
Sure, you have to be conscious of adding "where deleted_at = NULL" (or the opposite) to all your queries. If you're going through an ORM this is usually trivial e.g. in ActiveRecord it can be a default scope on your model.
On a proper database you can do your "undeleted" with triggers
and it's relatively trivial.
I like this solution as well, FWIW.
If I was retrofitting an existing application with soft-deletes I would definitely favor this solution.
There are some obvious advantages over a "deleted" column on your main table for sure.
One drawback is that you now have to keep two table definitions in sync. You also have to add conditional logic in a lot of places to handle whether a given piece of code is looking at a normal user from the "users" table or a deleted user from the "users_deleted" table. Instead of messing with the WHERE clause on every query, now you're messing with the table name on every query. So that's a wash IMO.