את עונת 04–2003 פתח ביורנדאלן בהצלחה, כשהוא זוכה ב-3 מתוך 4 התחרויות הראשונות, בקונטיולאהטי ובהוכפילצן. למרות זאת, בהמשך העונה ניצח בשתי תחרויות נוספות בלבד, כשהוא מסיים בחמש נוספות במקום השני ובשלוש במקום השלישי. הגם שהצליח לאסוף 901 נק' במהלך העונה, סיים במקום השני בגביע העולמי, כשהוא מפסיד ליריבו הגדול רפאל פוארה שזכה ב-1010 נק'. גם באליפות העולם היה בצלו של הצרפתי, כשפוארה זוכה בשלוש מדליות זהב, בעוד שביורנדאלן יצא ללא ניצחונות כלל, אבל זכה במדליית כסף במירוץ השליחים ובשלוש מדליות ארד - בספרינט, במרדף, ובתחרות האישית ל-20 ק"מ.
ארבעה גביעי עולם בחמש עונות.
עונת 05–2004.
עונת 05–2004 נפתחה מצוין עבור ביורנדאלן. הוא ניצח ב-2 מהתחרויות בביטושטולן ובאוסלו, והוביל את הדירוג העולמי לפני סוון פישר (גרמניה) ורפאל פוארה. הוא דילג על התחרויות באסטרסונד בשביל להתחרות בגביע העולם בקרוס-קאנטרי, ולכן ירד בדירוג העולמי למקום החמישי. לאחר שני מקומות רביעיים באוברהוף, זכה בחמש תחרויות ברצף ברוהפולדינג ובאנטהולץ, והוביל מחדש את הדירוג. הוא דילג שוב על תחרויות ההכנה למשחקים האולימפיים בסאן סיקריו, כמו גם על 2 מ-3 המרוצים בפוקליוקה. הוא השתתף במרוץ לזינוק המוני שם, וזכה בו בפער של למעלה בדקה.
באופן דומה, שלט ביורנדאלן באליפות העולם בהוכפילצן שבאוסטריה. הוא החל בניצחון בספרינט, ניצח במרדף וסיים את האליפות עם ניצחון במירוץ בזינוק המוני. בנוסף, זכה במדליית זהב עם נבחרת נורווגיה בשליחים, שזכתה לראשונה מאז 1967. המירוץ האישי ל-20 ק"מ היה היחיד בו לא זכה בזהב, כשסיים בו במקום השישי. המנצח היה הצ'כי רומן דוסטל. עם 4 ניצחונות באליפות העלה את מספר מדליות הזהב מאליפויות העולם ל-7.
בשל היעדרויותיו מתחרויות הגביע העולמי, דורג ביורנדאלן לפני תחרויות סיום העונה בחאנטי-מנסייסק רק במקום ה-3, אך ניצחון, מקום שני ומקום רביעי שם העניקו לו את הניצחון בגביע העולמי, כשהוא מסיים 11 נק' לפני סוון פישר. הוא השיג כך את גביע העולם השלישי שלו. במונחים אחרים, למרות זאת, ביורנדאלן היה עליון בצורה ברורה - הוא ניצח ב-60% מהמרוצים בהם השתתף (12 ניצחונות בסה"כ), סיים על הפודיום ב-75% מהם, ולא סיים באף מרוץ מחוץ לשישה הראשונים. מבחינות אלה, זו הייתה העונה המוצלחת ביותר עבורו.
עונת 06–2005.
את עונת 06–2005 פתח ביורנדאלן בהצלחה שוב, עם מקום ראשון ושני בשתיים מהתחרויות באסטרסונד והוכפילצן והובלה בגביע העולמי לאחריהן. כמו בעונה שעברה, דילג על התחרויות לפני חג המולד, הפעם כדי להתאמן. לאחר חג המולד חלה ביורנדאלן, ולכן נאלץ לדלג על התחרויות באוברהוף ורוהפולדינג. ביורנדאלן נאלץ לשהות שמונה ימים במיטתו ללא אימונים כלל, והחל להתאמן רק 6 ימים לפני התחרויות באנטהולץ. בשל כך, הוא ערך שני אימוני סקי, אבל לא אימוני ירי. לאחר שבעה מרוצים בהם לא השתתף, ירד למקום ה-12 בדירוג העולמי. עם שני מקומות חמישיים וניצחון באנטהולץ, לפני האולימפיאדה, חזר ביורנדאלן להתחרות.
בשל המחלה ואיבוד ימי האימונים, אולימפיאדת טורינו לא הצליחה לביורנדאלן כפי שציפה. גלישתו הייתה איטית מהצפוי, הוא קלע באופן הססני, והתאפיין מלבד זאת בהרבה מזל רע. הוא הגיע כאלוף האולימפי ב-4 מתוך 5 התחרויות (המירוץ בזינוק המוני לא היה קיים בסולט לייק סיטי), אבל הוא לא הצליח לזכות באף תחרות. הוא פתח עם מדליית כסף בתחרות ל-20 ק"מ, אבל בתחרות הספרינט סיים במקום ה-12. בתחרות המרדף, התקדם ביורנדאלן ונראה כי זהו סיכויו לזכות בזהב, אבל הפסיד באורח לא אופייני לצרפתי וינסנט דפראן בספרינט לקו הסיום. בתחרות השליחים, למרות הופעה טובה, הצליח להחזיר את הנבחרת הנורווגית רק למקום החמישי מהמקום השמיני (הנבחרת הנורווגית כולה התאפיינה בכושר לקוי באולימפיאדת טורינו). בתחרות הזינוק ההמוני הוביל עד לקליעה האחרונה, אך החטיא שם שתי מטרות וזכה לבסוף במדליית הארד. הביאתלט המצליח ביותר באולימפיאדה היה הפעם מיכאל גרייס (גרמניה).
את העונה בגביע העולמי סיים ביורנדאלן בהצלחה. הוא ניצח 3 פעמים בפוקליוקה ובקונטיולאהטי, והגיע לפני המפגש האחרון באוסלו כשהוא מדורג במקום השני בדירוג העולמי. לאחר הניצחון בספרינט, בו הגיע פוארה למקום ה-46, לקח ביורנדאלן את ההובלה. שני ניצחונות נוספים בשתי התחרויות הנותרות באוסלו הובילו אותו לזכייה בגביע העולמי הרביעי שלו, בפער של 119 נק'.
עונת 2006-07.
את הענה פתח ביורנדאלן באופן מושלם, כשהוא מנצח בחמש תחרויות רצופות בשתי העצירות הראשונות בסבב גביע העולם, אסטרסונד והוכפילצן. את מרוץ המרדף ביורנדאלן ניצח באחד הפערים הגדולים מעולם, למעלה מ-2 דקות. הדומיננטיות הזו נשברה על ידי מיכאל גרייס, כשדילג על התחרויות הבאות בהוכפילצן (הועברו לשם מאוסרבילה) ובמקום זאת התחרה בתחרויות בקרוס-קאנטרי בלה קלוסאז. ב-30 בדצמבר השתתף באתגר העולמי הקבוצתי בגלסנקירכן, כשהוא מנצח בו פעם רביעית ברציפות, בפעם השנייה עם לינדה גרובן. באוברהוף, כשהוא יורד מאימוני גובה, קליעתו הייתה גרועה, וסיים במקום 30 בתחרות הספרינט. באמצע ינואר זכה בשתי תחרויות ברוהפולדינג, בנוסף להובלת נבחרת השליחים הנורווגית לניצחון. שבוע מאוחר יותר דילג על התחרויות בפוקליוקה כדי להתאמן לקראת אליפות העולם.
את אליפות העולם בביאתלון באנטהולץ ביורנדאלן פתח בהצלחה עם שתי מדליות זהב בספרינט ובמירוץ המרדף העוקב. אחרי מרוץ אישי ל-20 ק"מ מאכזב, בו סיים במקום ה-32 כשהוא מחטיא 6 פעמים, הוא זכה במדליית כסף עם נבחרת השליחים הנורווגית. במירוץ הזינוק ההמוני סיים במקום הרביעי, כש-4 החטאות בשתי עמדות הירי בעמידה עלו לו בניצחון. כדי להשתתף באליפות העולם בסקי נורדי בסאפורו דילג על התחרויות בתחילת מרץ בלאהטי, פינלנד. שבוע מאוחר יותר חזר לסבב באוסלו וניצח שם פעמיים.
למרות 11 ניצחונות בעונה, ושיעור ניצחון של 58%, ביורנדאלן לא הצליח לזכות בגביע העולמי בו ניצח מיכאל גרייס (גרמניה) בשל היעדרויותיו הרבות, כשהוא מדלג על שמונה מרוצים בהוכפילצן, פוקליוקה ולאהטי.
עונת 2007-08.
בעצירה הראשונה של הסבב העולמי בקונטיולאהטי, במירוץ השני של העונה, ספרינט, זכה ביורנדאלן. במרדף הוא סיים מקום שני. לפני חג המולד, הוא זכה פעמיים נוספות והשיג עוד מקום שני בתחרויות בהוכפילצן. הצלחתו המשיכה בינואר, כשבאוברהוף וברוהפולדינג הוביל את נבחרת השליחים הנורווגית לניצחונות. בנוסף לכך, הוא ניצח בתחרויות בזינוק המוני ברוהפולדינג ובאנטהולץ. באליפות העולם באסטרסונד הוא בלט ביחד עם בן טיפוחיו אמיל הגלה סוונדסן (נורווגיה) ומקסים צ'ודוב (רוסיה). הוא זכה בתחרויות האישיות במדליית זהב במירוץ המרדף, בשתי מדליות כסף (מרוץ אישי ל-20 ק"מ ומירוץ בזינוק המוני) ובמדליית ארד (ספרינט). בנוסף, במירוץ השליחים זכה ביחד עם הנבחרת הנורווגית בכסף. כך זכה במדליה בכל אחד מחמשת האירועים בהם השתתף. בתחרויות סיום העונה בחנטי-מנסייסק, רוסיה, זכה ביורנדאלן במירוץ הספרינט, מה שהיווה את ניצחונו השביעי לעונה. בנוסף, הוא השיג את הגביע העולמי החמישי שלו.
עונת 09–2008.
לקראת עונת 09–2008 הכריז ביורנדאלן שיתמקד בניסיון לזכות בכמה שיותר מדליות באליפות העולם שהתקיימה בפיונגצ'נג. מלבד זאת, הוא סבל מתסמינים של מחלה ארוכה שתקפה אותו לפני פתיחת העונה. הוא החל את העונה עם שני מקומות שניים באסטרסונד ובהוכפילצן, אך המחלה הובילה אותו לתוצאות לא יציבות לפני חג המולד. תוצאותיו התייצבו יותר אחר-כך, עם מקום שלישי במירוץ הזינוק ההמוני באוברהוף. בעצירה האחרונה בסבב לפני אליפות העולם השיג שני ניצחונות בספרינט ובמרדף העוקב ברוהפולדינג, והציב עצמו פעם נוספת כאחד המועמדים הבולטים לניצחונות באליפות העולם.
אליפות העולם בפיונגצ'נג הייתה מוצלחת במיוחד עבורו. הוא החל בזכייה בתחרות הספרינט, ואז זכה בתחרות המרדף. זכייתו שם לוותה בשערורייה מסוימת. ביורנדאלן הוביל במהלכה קבוצה של לפחות 15 גולשים אחרים, בטעות, מעל לגשר במקום לצידו. לאחר תלונה מהמשלחת הרוסית, חבר השופטים החליט לתת לכל הקבוצה עונש של דקה שתתווסף לזמניהם, מה שהוריד את ביורנדאלן למקום השלישי. תלונה נגדית על ידי המשלחת הנורווגית ושבע משלחות אחרות החזירה את התוצאות לקדמותן, לאחר שנקבע שהטעות לא חסכה להם מרחק. ניצחון זה היה חשוב במיוחד עבורו, כי היה זה ניצחונו ה-85 בביאתלון וה-86 בכלל (כולל ניצחנו בתחרות קרוס-קאנטרי בגאליברה), ובכך הוא השווה את שיאו של אינגמר סטנמרק למספר הרב ביותר של ניצחונות בספורט שלג. חילופי המהלומות המשיכו ארבעה ימים מאוחר יותר, כשהמשלחת הרוסית האשימה את ביורנדאלן בחסך לעצמו 400 מ' בתחרות הספרינט כמה ימים קודם לכן, טענה שהתבררה על ידי חבר השופטים כטענת שווא. לאחר מכאן זכה במירוץ האישי ל-20 ק"מ, התואר העולמי הראשון שלו במקצה זה, וביחד עם נבחרת השליחים הנורווגית, והפך לביאתלט שזכה בהכי הרבה מדליות זהב באליפויות עולם בכל הזמנים, כשהוא זוכה ב-4 מתוך 6 מדליות הזהב האפשריות.
אחרי האליפות, הגיע למקום השני בספרינט בתחרויות הקדם-אולימפיות בוויסטלר, ולקח את ההובלה בגביע העולם. הוא הגיע למקום שני בספרינט בטרונדהיים, ולאחר מכן השיג שני ניצחונות במרדף ובמירוץ בזינוק המוני שם, באחרון כשהוא מנצח ללא החטאה. עם מקום שני בספרינט בחנטי-מנסייסק, הוא הבטיח את גביע העולם השישי שלו לאחר תחרות צמודה לאורך העונה עם אמיל הגלה סוונדסן (נורווגיה) ותומאש סיקורה (פולין).
עונת 2009-10.