I'm not a fan of soft-deleting. Threads that have been soft-deleted are an eyesore and a distraction while you are trying to manage the forum. If you've just deleted 20 Viagra/Cialis threads sprinkled throughout the site, it's just not good to continue to look at them after you've deleted them. For forums that have split admin and moderator functions, maybe that's useful. For people who moderate their own forums, not so much.
As for the second solution, it seems to be an overkill to create a private forum just for the purpose of undeleting threads, which you only have to once in a blue moon. Besides, that's not a very neat solution, because you would have to figure out which sub-forum the thread originally came from (not a slam dunk issue for forums with lots and lots of sub-forums).
It just seems easier to give admins an option to "trash" threads instead of permanently deleting them. That's a very easy metaphor to absorb for people who use modern operating systems, where everything can be recycled/trashed.