LEADS: Nothing gets lost when going from leads to company - the original information is maintained under the lead. The Opportunity is tied to the original lead so you can get back there.
Leads keep the data separate but they complicate things. Unless you really have a purpose for keeping some data separate, I would think twice about leads.
BULK DELETES: We've written several different variations on bulk deletes over the years depending on specific needs. Your particular case doesn't seem like much of a need to do that though. Just stop marketing to those people - take them out of your groups.
Most people keep the names and activity around for historical analysis purposes - to see what works, what doesn't, activity history, etc.
What are you really trying to accomplish? You trying to keep your database small? 2K records isn't much.
The real question: Is this for you or for a client? If for a client, my team is always available to help if you want to make sure it is successful. 100% less headaches for you plus a markup on our services plus a very happy client.