Medina only fought once in 2004, defeating Leonardo Resendiz on July 23 at Rancho Mirage, California by a third-round knockout, to win the WBA's regional NABA super featherweight title. He was to fight José Miguel Cotto on August 20, 2005 in Ponce, Puerto Rico. Had he beaten Cotto, he would have put himself in a position to challenge for the WBO super featherweight title. Cotto was not able to reduce weight to the super featherweight weight limit, however, so the fight was suspended. On 31-05-2006 he fought Cassius Baloyi for the IBF super featherweight title, the same title he'd challenged Molina for back in 1993, and lost by 11th-round TKO. Medina returned to outpoint Kevin Kelley by a twelve-round majority decision, then fought a rematch with Baloyi on 05-07-2007 which was scored a technical draw after Medina suffered a cut from an accidental clash of heads. In his final fight, Medina lost by a two-round TKO to Malcolm Klassen. These final three bouts were all IBF super featherweight Title Eliminators. Medina has a record of 64 wins and 15 losses in 78 professional boxing bouts, with 30 wins by way of knockout.