En 2004 el Gobierno presentó un proyecto de Ley de Alternatividad Penal que contemplaba la suspensión de las penas para los jefes paramilitares, si el presidente de la República lo solicitaba, y la prohibición de ejercer funciones públicas por cinco años. Dado que el marco estaba enmarcado en la modificación de la ley de Orden Público se daba por hecho que la extradición no sería aplicada, pues a los paramilitares se les consideraba entonces como «sediciosos», categoría inscrita en el delito político. A pesar de las mayorías de Uribe en el Congreso, este proyecto generó rechazo porque violaba el Estatuto de Roma. El Gobierno lo retiró el 15 de junio de 2004. Mientras tanto, un grupo de congresistas de diferentes bancadas prepararon un nuevo proyecto que se ajustara a los estándares internacionales.
Discurso del ex-jefe paramilitar y comandante de las AUC
Salvatore Mancuso en el Congreso de la República de
Colombia y reacción de una víctima presente en el recinto.