It took the petitioner in Doe v. Immigration & Customs Enforcement, __ F.Supp.2d ___, 2006 U.S. Dist. LEXIS 28300 (S.D.N.Y. May 16, 2006) several years and two district court decisions to get his record expunged. Take a look at the orders in that case, which describe the process for expunging an incorrect NCIC record. Thanks to Dan Kesselbrenner.