The legal answer is that tax liens can remain for up to 7 years from the date paid.
The exclusion period of 7 years does not begin until the debt is paid.
See FCRA 605(a)(3).
Two general procedures might be used to obtain removal prior to the statutory exclusion date of 7 years from date paid.
First is to obtain a formal vacature of the lien. For federal tax liens, for example, the IRS has a procedure for withdrawal of their liens if paid in full. One paid, a form is then submitted to the IRS requesting withdrawal. If paid in full, the IRS will grant withdrawal. Otherwise, they will only discharge the lien.
The CRAs will remove a withdrawn federal lien, but not a discharged lien.
The second basis for removal of a tax lien is if the CRA data obtained from the public record does not contain adequate identifying information.
The CRAs have agreed to remove tax liens that do not include the consumer's name, address, and a full SSN or date of birth.
That recent removal policy is set forth in their National Consumer Assistance Plan.
