Highlander
Not all Immortals try to behead one another. Many become friends or allies with each other, especially heroic ones, while others just try to stay out of the Game. It should be easy to establish Immortal PCs as having that kind of relationship.
d20 Modern/Past, etc., have magic. But it comes later through advanced classes, so it doesn't overpower the normals. It makes for a low-magic setting, which suits Highlander in most cases.
I think the flashbacks could work. One adventure could be set in the modern day, the next in the past. d20 Modern doesn't depend on magical equipment, and nor does Highlander. The characters only need to purchase new gear or make new Wealth rolls. They might have only a favourite sword they keep with them, but that can be re-bought in Wealth checks.
Ah, the characters might have different levels of experience in the past, but one can assume their skill level fluctuates with practice and the era they live in. Or build characters at a certain level and don't or rarely level. Immortals in Highlander don't seem to get significantly better with age anyway. (Okay, maybe a less level-based system would be more appropriate.)
Another problem is continuity. If characters just met in the modern age, then they can't have met in the past. It would be necessary to have "broad brushstrokes" backstories and assume the PCs have always been acquaintances some time earlier in the past. That's how the Highlander movies and series seem to play it. The other issue is being unable to have adventures set before characters were born. This can be resolved by the GM establishing a starting date. Or play through in chronological order from to past to present.
I vote d20 Modern. It's less magic-based and encompasses different time periods. It can have antique swords and guns and hoverboards from the alien planet of Zeist. :D