But when the politician disappeared and Nixon got re-elected wouldn't that lead to the future the politician need to travel back in time to prevent that happening?
Nope, he created a paradox, in spite of the "paradox free time travel". You can go and do "what always happened" and you can interact with yourself for a bit, but you can't change your entire life and the thing that caused you to go back in the first place, not without doing something to set up a loop.
Now, if he'd travelled back in time to the day he was born, and then taken the baby on a timetravel trip to age super fast, then brought the baby back to present day as an adult, it would have been the same as what happened with Hermes 2 and "Lars", and would have just resulted in a paradox duplicate and probably would have worked out.
Or he created a timeline where Nixon ran unnopposed, so that alone is enough to change… something.
Failing that. The thousands of Bender's broke reality at the end of the movie, and since then, the proffessor, fry and Bender traveled forward in time through three cycles of the universe. Can just say the rules are broken are different now, if you really need an alternate explanation.
Or. Its the usual philosophy of a joke being more important than exact continuity, its just a show and we really should relax.