I also got confused by the timeline of him getting deported from Russia. I think he's allowed to fly out as long as he returns and continues the journey on foot. You can see on the world map of the journey he makes steady progress from 1998-2006 but then he doesn't finish crossing Siberia until 2017.