It wasn't out of the question, having observed Ukrainian elections firsthand for the past decade-there's a gray line between Fraud and Voting
Stuffed ballot boxes, spoiled pro-western ballots, re-written results, pre-written results and ballot swapping are clearly fraud and can be exposed as such
Food handouts, soup kitchens at voting stations, tough "Reporters" with scarred faces and black leather coats at polling stations, Family members in counting committees-can be stopped at a cost
The Main chance he had of winning (Take a look at the 1998 election result, you see a lot of red right there), Is the fact that the Soviet Union (Like a good Hearts of Iron player) liked Heavy Industry, even the sort that made a net loss. These industries go bust, are bought up by some clever fellow (Mostly Directors), who then buy up the housing of the workers. Thus, The Oligarch pays them, they pay him rent, he uses this to get elected and ensure his company stays subsidized, and the cycle repeats. If Ukraine has more of that, it stays in a post-communist self-sustaining mechanism for a good few decades more, and decays.
If he had the PR campaign of 2010, He'd have been golden-moderate Oligarchs (The Current President included) would have backed him, tried to move him to the center, the Opposition would have fractured and 2010 would have come early. Timoshenko would possibly have been a rallying figure in this world after Yuschenko's electoral failure.
Also Yanukovich 2004 was rather different from Yanukovich 2010, less PR aware, More Kuchma dependent-with a lot of the old Kuchma lot carrying over. Maybe they would have prevented such dramatic fiscal collapse as we saw in 2012-13.
Overall, its' hard to judge the result of all the 2004 Yuschenko optimism genuinely losing, by a comfortable margin-we may even have seen West Ukraine try and ring-fence itself against the Post-Soviet Kuchmaland which would tighten its' grasp on the rest of the place.