Gleichzeitig begann der MAD unter Gramms ministerieller Fachaufsicht bereits kurz nach dem Auffliegen des NSU am 4. November 2011 damit, Akten über die rechtsextremistische Betätigung von Bundeswehrsoldaten zu vernichten. Betroffen hiervon waren siebzehn Dossiers, von denen angenommen wird, dass sie Aufschluss über das Unterstützerumfeld des NSU hätten geben können. Nachweislich befand sich unter den geschredderten Akten ein Dossier über die neofaschistische „Fränkische Aktionsfront“, zu deren führenden Mitgliedern zumindest eine Person zählt, die Kontakt zu dem NSU-Terroristen Mundlos gehalten hat. Ein Ende fand die Aktenvernichtung seitens des MAD erst Mitte Juli 2012 – auf förmliche Anweisung des Vorsitzenden des parlamentarischen Untersuchungsausschusses.