The way I see it, there are two explanations, one tricky, and one fairly easy. Either alternate timelines had a play, or Braxton never interfered with the "Timeless" incident.
The Tale of Two (or four) Braxtons
The last time we saw Braxton was in "Future's End, Part II", when he arrived in his timeship to restore Voyager to its original place in the Delta Quadrant. Rather than have Voyager find their own way home in a similar manner as the Enterprise-E in First Contact, they introduced a second Braxton. But what of the Braxton who spent 30 years on Earth? Surely he didn't just vanish. Sure, the new Braxton helped out Voyager, but there's still a raving old hobo who crash-landed on Earth 30 years prior. It would seem that there are parallel timelines going on here.
This sets up a way to explain "Relativity" fairly easily. The Braxton in this episode is the who spent time on Earth, he says so himself. Because we've already seen an alternate version of Braxton interact with our timeline, it not too far of a stretch to think that our Braxton did timeline cleanup in an alternate timeline. Considering that he'd be in pretty bad shape after his exile on Earth, he'd be fairly prone to mistakes. He did end up killing multiple versions of Seven of Nine before finally apprehending his future self, and that's not usually something a completely stable officer would allow to happen.
The Three Incursions
The easier explanation comes from Braxton's own words to Janeway. He specifically mentions that he cleaned up "three" major temporal incursions. At that point in the series, there were five. In order, they were "Time and Again", "Year of Hell" "Future's End", "Timeless", and "Endgame". It's entirely possible that he didn't get to intervene in "Timeless". After all, one ship living or dying is one thing, but "Time and Again" was an entire planet, "Year of Hell" was an entire region, and "Endgame" was the entire Borg Collective. I find it easy to believe that either he didn't get to "Timeless", or that as a result of investigating the other incidents, it was determined that the event should stand. This would certainly be frustrating, and given his already fragile mental state, potentially debilitating to the point of temporal psychosis.
