Going through a massive database cleanse, have tried everything I can think of and read through all the doc and discussions but can't find anything regarding whether it is possible to archive leads rather than delete them. I'd rather preserve all of their information in case they ever enter our system again. If it is possible to archive, does the number still count against our DB size?
I agree, to preserve information for reporting as well as dedupe in the future, you do not want to delete them. So what you can do is perform several functions in order to make sure they are not marketed to (ex. blacklisted or marketing suspended). However, they will still remain in the database and count towards your database limit.
Another option is to create a new lead status for these leads so they are easily recognizable.
Here are a couple discussions from the past with a similar question:
Is there a way to archive bad leads? Unsubs?
Leads deleted in SFDC (this one suggests that "archiving" is available through partitions with a Marketo Enterprise account)
Enter your E-mail address. We'll send you an e-mail with instructions to reset your password.