First thing's first, you need to get a good backup of that database. Next run a DBCC CHECKDB to ensure that after years of neglect that it is still consistent.

After that, if you can temporarily change the database to simple recovery then your deletes will go much faster, as they are not getting logged.