How to keep a chase interesting?

[weckar]

I've got my players chasing a villain all across a continent. The villain is trying to trigger an end-of-the-world prophecy, and is low on allies (by choice).
Problem is, I am having trouble keeping the chase interesting while also keeping the players behind. They are currently in his old bastion looking for clues to his whereabouts, but I feel I can't be too transparent lest they run straight for him. At the same time, I am having trouble providing intermittent threats and quests that actually interest them.
How exactly can I run this without just having them walk the continent from point where they just miss him to the next? One player in particular has already made clear they have inconsequential combat so relying on random encounter tables is right out.

[Malroth]

He's on his last legs and out of allies? Let the Pc's catch him trying to recruit more and end his story arc with him. Then have a new badguy appear with a new goal taking advantage of the chaos left in the wake of the first villians demise.

[weckar]

No, not that at all. He is actually doing quite well. He... just prefers not having to deal with allies.
Replacing the villain at this point is quite impossible, as removing him from the picture would literally resolve the whole campaign. There would be no chaos.

[PoeticallyPsyco]

Have the villain create disasters (undead armies, citywide fires, assassinations with massive political fallout; whatever fits best), so the heroes are slowed down as they stop to prevent them or provide relief. Similarly, dealing with traps and such he/she left behind as they follow his/her trail. The variety of encounters should keep things fresh, and if you let the players know that they're getting ever closer the two together should be enough to keep them hooked. Maybe throw in an unrelated problem every now and then for variety's sake.

[Helluin]

Can we get information on what this prophecy entails, and how the Gillian is triggering it?

[Eldariel]

Acquiring information can take encounters. Some people know stuff, but e.g. Thieves' Guild would never sell anything for free. The party needs to convince them of not selling the guild out on the information source, and the guild to sell it to them in the first place (and indeed, even finding guild contacts).

Same kinds of considerations can apply with sages, soothsayers, etc. Information gathering can involve social encounters, combat, dungeons, etc. depending on who has what you need and what kinds of services do they need in return (and how to find them in the first place).

Same with the hunt: just because he has no underlings doesn't mean that the locations he visits have no guardians. Perhaps the BBEG is able to avoid and subvert them, but unless the PCs know as much as they, the PCs would have to engage said protections.

[RNightstalker]

How about letting the party capture/kill him, only for him to escape/resurrect, a la Joker in The Dark Knight or an immortal a la Highlander, needs to lose his head?

[Eldariel]

Rival group with similar goals believing the party incompetent/weakening their chances and thus ending up beating the party to various checkpoints lest the party make haste, and even potentially fighting the party to keep their cover/whatever could work too (a recurring nemesis party). A cliché, but not all clichés are bad.

[Segev]

What are the PCs' transport options? The answers to keeping a chase interesting and prolonged are very different if they have to trek or sail across the distance, can ride fantastical carriages and supersteeds across the distances, can fly in a powerful airship, or can teleport.