I have found that the best way to do this is the backup (stsadm) each
WSS sites individually on a nightly basis. Although this does take a
significant storage to do so, it allows us to restore individual
files/site collections for the users without inhibiting all sites in
the environment.

To restore a document, I would restore the site under a new temp url
and get the document  requested and upload it to the original site, then
delete the temp site that I restored to get the document out. I find
it only takes about 5-10 minutes to get the file. Although an admin
has to do it, it give some sort of recourse in case of extreme
emergencies. I don't advertise that this is available - but use it as
a fail-safe... Not sure how well this would work in an environment of
your size though.

I wrote a custom application that I scheduled to run off hours for our
environment and backup structure but have not had the time to abstract
this out so I could really share it with the public.

I've also heard great feedback on the MindSharp Recycle Bin solution
available as premium content on their web site ... but this is a more
manmanual process for people without admin rights and does not apply as
globally as the solution I outlined above.

I used this approach for a while. I had to stop though, as it didn't scale
well. First, it's not very fast. We could only get 12 to 13 GB an hour out of
STSADM when writing the backups. Once we got into the several hundred GBs of
data it just took too long. Second, earlier versions of STSADM would lock
content databases if it was backing up a site with a lot of rows in the Docs
table. That's been mitigated in patches, but it's still a possibility.
Finally, you cannot restore an STSADM backup of a Site Collection into the same
content database that the original is in. Now that we have several content
databases it's less of a problem, but originally we just knew that sometimes we
couldn't restore our backups and we didn't know why.

For small deployments though, this is a great piece of the disaster recovery
plan.

Since we do a database backup every night, the best way that I've found
to restore a single file, or a small set of files is to use the
SharePoint Database Explorer from James Edelen, which can be found here:
mindsharpblogs.com/.../189.aspx

We take the nightly backup for the day that the restore has been
requested from, and restore the database to any database server. You
can then crack open the restored database with the SharePoint Database
Explorer and quickly navigate to the file(s) that need to be restored.
From there you can choose to save the original file back to a file
system or even save the document  versions out to the file system. Once
you have your files, you can just put them back into SharePoint where
they should be.

The nice thing with this strategy is that we are using the same backups
that we are creating every night as well as not having to bring the site
back up into a working SharePoint environment. The only limitation we
see is not being able to restore list items.

However, remember to only use this utility against a backup of your
database, never use it on a production database.