W dwóch kolejnych sezonach nie stawała na podium zawodów pucharowych. Najbliżej tego celu była 16 stycznia 2005 roku w Novym Měscie, gdzie zajęła czwarte miejsce w sprincie stylem klasycznym. W klasyfikacji generalnej Pucharu świata zajmowała kolejno 23. miejsce w sezonie 2003/2004 i trzynaste w sezonie 2004/2005. Podczas mistrzostw świata w Oberstdorfie w 2005 roku zajęła 15. miejsce w sprincie klasykiem i 23. w biegu łączonym. Na podium zawodów Pucharu Świata wróciła 5 lutego 2006 roku, kiedy zajęła trzecie miejsce w biegu na 10 km stylem klasycznym w Davos. Był to ostatni start pucharowy przed igrzyskami olimpijskimi w Turynie. Majdič uplasowała się tam na szóstej pozycji w biegu na 10 km klasykiem, ósmej w sprincie stylem dowolnym, jedenastej w biegu łączonym oraz czternastej w biegu na 30 km techniką dowolną. Po powrocie do rywalizacji pucharowej już w pierwszym starcie ponownie stanęła na podium, tym razem zajmując trzecie miejsce na dystansie 45 km klasykiem w Mora 4 marca 2006 roku. W pozostałych zawodach punktowała czterokrotnie, w tym 9 marca 2006 roku w Drammen odniosła swoje pierwsze pucharowe zwycięstwo, wygrywając sprint techniką klasyczną. Sezon 2005/2006 zakończyła na dziewiątym miejscu. thumb|250px|Majdič w 2009 roku Pierwszy medal w karierze zdobyła na mistrzostwach świata w Sapporo w 2007 roku.