The state of Virginia must be on a house cleaning mission to clear up old tax debts, as we have had numerous questions come through this forum the last couple of weeks about the very same issue.
I know this will not help your situation, but I ran across a web site the other day with posts from hundreds of people on this very same issue, and I thought you might find it interesting to at least know you are not alone in this.
As far as the collection of tax, Virginia has a statute of limitations of 20 years to collect taxes from the date they were finally assessed. Please refer to the following link from the Virginia Code that outlines this statute.
You do, however, have the right to deal directly with the state on this issue rather than the collection agency. If you would prefer to do so, simply write the collection agency a letter stating your intentions to deal with the state on this matter.
The state has apparently turned over a large number of old tax debts to this collection agency, which in my opinion leads me to believe that for all practical purposes they have written off their collection attempts due to the age of these debts. If that is the case and you choose to deal directly with the state, it is possible at this point that they might be willing to accept an offer to settle the debt for a lesser amount than they show is due.
If this has been helpful please press the Accept button. Positive feedback is also appreciated.