W 2004 roku zespół w końcu znalazł nową wytwórnię, Crown Japan, pod którą 21 maja 2004 został wydany, tylko w Japonii, ich trzeci album "Here We Go Again". Poza Japonią album był dostępny tylko na drodze importu na oficjalnej stronie zespołu. Album nie uzyskał żadnej uwagi, nie dostał się na żadną listę przebojów, co udowodniło po raz kolejny handlową klapę. Pomimo tego, zespół Bowling for Soup, będący bliskim przyjacielem z SR-71, nagrał cover ich piosenki "1985 do albumu A Hangover You Don't Deserve, wydanym w późnym okresie 2004 roku. "1985" został wydany jako singel i osiągnął 23. miejsce na Billboard Hot 100.
Tytułowy utwór "Here We Go Again" został również ponownie nagrany w 2006 roku do albumu Call It What You Want przez poppunkowy zespół JParis. Mitch Allan wyprodukował album zespołu.
Pierwszy utwór z albumu, "Axl Rose", ukazał się później jako singiel, razem z "Here We Go Again" i "All American" wydany jako B-side. Cover "In Your Eyes" oryginalnie wykonanego przez Petera Gabriela, również ukazał się jako singiel i był często grany przez zespół na trasie koncertowej w latach 2004-2005.