In der Saison 2003/04 errang Andersen mit drei Top-Zehn-Platzierungen den achten Platz in der Weltcupwertung über 1500m, bei der Mehrkampfeuropameisterschaft 2004 in Heerenveen den 12. Platz im Großen Vierkampf und bei den Einzelstreckenweltmeisterschaften 2004 in Seoul den 16. Platz über 1000m sowie den 15. Platz über 1500m. In der folgenden Saison holte er in Baselga di Piné in der Teamverfolgung seinen dritten und damit letzten Weltcupsieg und erreichte mit drei Top-Zehn-Platzierungen den neunten Platz in der Weltcupwertung über 1500m. Beim Saisonhöhepunkt, den Einzelstreckenweltmeisterschaften 2005 in Inzell, gewann er in der Teamverfolgung und über 1000m jeweils die Bronzemedaille. Außerdem belegte er dort den 22. Platz über 500m sowie den vierten Rang über 3000m und bei der Sprintweltmeisterschaft 2005 in Salt Lake City den 16. Platz im Sprint-Mehrkampf. In der Saison 2005/06 kam er mit vier Ergebnissen unter den ersten Zehn erneut auf den neunten Platz in der Weltcupwertung über 1500m und absolvierte in Heerenveen seinen letzten Weltcup, welchen er auf dem neunten Platz über 1500m beendete. Bei der Sprintweltmeisterschaft 2006 in Heerenveen belegte er den 31. Platz im Sprint-Mehrkampf und beim Saisonhöhepunkt, den Olympischen Winterspielen 2006 in Turin, den 18. Platz über 1000m sowie den siebten Rang über 1500m.
Andersen wurde viermal norwegischer Meister über 1500m (1998, 2001, 2003, 2006), dreimal über 1000m (2003, 2004, 2006), zweimal über 500m (2004, 2006) und einmal im Großen Vierkampf (1996).