As the question states, I’m looking for a monster that can stalk the party for the latter half of a campaign I’m running. They are only level 3-4 so it would have to be something way too strong to fight head on but preferably slow or stupid or both so they have the chance to escape it. I of course plan for them to be able to slay this monster once they gain 7-10 levels.
A Revenant would be the archetypical thing who is out to get someone, no matter what. Though Revenants are about dishing out revenge to whoever killed them, a smart BBEG might be able to trick one to track the party instead. Maybe the party carries a MacGuffin that makes the Revenant track them instead of the real murderer. The downside is, as level 6 creature, a party around levels 10-14 is going to make short work of an elite Revenant, if it doesn't pack some serious backup.
A Golem is another monster that mindlessly pursues whatever command it was assigned. There are at least thirteen different golems in the bestiaries. A mighty Elite Iron Golem is loaded with immunities, so one would be bad news even to a higher level party. Oh, fire heals it, it's got a poison breath weapon, reach 10', and anti-magic field too! Not to mention damage resistance 15/physical and AC 34.
A nasty surprise would be a Carrion or Flesh Golem. After getting some punishment from over-confident party, the golem reveals itself as an Iron Golem in a Terminator 2 like scene. If your players are fans of 90's action movies, that would probably be an excellent clue for vacating the premises as fast as possible. Having the golem a bit broken would explain why it can be outrun - for time being. After revealing itself as Iron Golem, it would repair itself for each encounter so in the final encounter, it cannot be outrun anymore.