Stories like the one you've mentioned are a staple of b-grade romance from Japan.

While it is a familiar "trope" I have not personally watched/read/etc much of it. I did watch a pg-13/mecha/lesbian anime featuring that as a premise, but I can't remember the name. It was underwhelming on a lot of levels, but I think I understand why people tend to use it in RP frequently.

Essentially, it's an easy way to get two characters into a relationship with minimal effort and maximum angst. If the characters have zero chemistry or hate each other, they will still hang out with each other to fulfill the prophecy, find their one and only, etc. In fact, not meshing well is [i]better[/i] because it amps up the conflict. This also guides the characters away from less abusive relationships because they don't have the "mark." Even if you're not into all of that crap, it's an easy hook up. You don't need to think of an excuse for these characters to come together beyond "oh look, they have [color=orange]「THE MARK」[/color]! Guess I'd better get to know them so that we can pork."

So while I don't know when it started online, I know it's been going around Japan for a while. But I think the reason it caught on is because it cuts to the "romantic" part instantly while bypassing all that "annoying" stuff like discovering each other. And for those who love angst, it's a low effort way to make sure a toxic relationship lasts well beyond its shelf life. But like all things RP, how good it is depends on how much effort you and everyone involved with it puts into it.