NOTE: This is valid for books only. In the Show, as of Season 7, annulments can be granted regardless to consummation.
Annulments in other faiths
We do not know anything about how annulments work with adherents of Red God, Drowned God, Many Faced God and Old Gods. There is not a single mention of an annulment in followers of those faiths. So the answer, with a heavy heart, would be we do not know yet.
Are Political marriages "De jure" invalid?
Also your assumption that most weddings in Westeros are de-jure invalid because of political nature is wrong. There have been plenty of political marriages in real world as well and none of them are considered "de-jure invalid".
It does not matter whether a marriage is political or not, if both parties said their vows, their marriage is de-jure and de-facto valid and binding.
As evident from your comments, you seem to be viewing Westerosi weddings in light of modern day real world. Marriage of convenience is an idea of modern world and the laws against it are targetted mostly to avoid immigration frauds. In Westeros, most High-born marriages are performed to gain some sort of advantage and there is absolutely no concept of a "Marriage of convenience" in Planetos or any law which declares them invalid. That's your personal idea which has and should not have any impact on the world set in A song of ice and fire.
To clarify, De jure does not mean "Legal according to laws of USA or Italy". De Jure means "Legal according to laws of the land/World concerned". Since there is no law against political marriages in Westeros, They are most definitely valid. I am surprised this actually requires logical proof but think of this logically.
How can something be invalid by law if there is no law making it invalid?
Faith of the Seven
We know of only one faith whose method of annulment is described in canon sources. That's faith of the Seven.
Weddings can be annulled by High Septon or a council of faith if:
- Wedding has not been consummated
- At least one party petitions the High Septon or council to annul their marriage. Example would be King Baelor's annulment of his marriage to Daena the Defiant.
As GRRM said:
Tigers14: btw, can a marriage be annulled without both parties
present? and without sansa revealing who she really is?
GRRM: no one needs to be present to annul a marriage
Tigers14: how?
GRRM: but Sansa would need to request it
Tigers14: as sansa?
GRRM: Well, why would a High Septon consider a request from anyone
but the parties involved?
Weddings can also be annulled if:
- Wife joins Silent Sisters. Example would be how Ser Quentyn Ball sent his wife to Silent Sisters so that Ball could be eligible for celibate criteria of King's Guard.
- One or both parties were coerced into marriage at sword point as vows sworn on sword-point are considered invalid.
Case of Robb
In Robb's Wedding, Robb followed the old gods while his wife Jeyne Westerling followed the faith of Seven.
As GRRM confirmed that Sansa can petition to High Septon for annulment of her marriage to Tyrion despite following the Old Gods herself, it appears that if one party adheres to faith of Seven (Tyrion did), both parties reserve the right to petition the High Septon to annul the Wedding provided it has not been consummated.
So in theory, Robb could appeal to High Septon for annulment if he had not consummated the marriage.
Then you wonder, why didn't he? Because:
- He did not want to. He was apparently head over heels in love with Jeyne Westerling and had absolutely no desire of leaving her.
- He was also too honorable to leave a woman with a bastard/shame of sex outside wedlock.
- He had consummated his marriage numerous times and thus was not eligible to apply.
He sought to rebuild his Frey alliance by offering them hand of his uncle rather than petitioning for an annulment. In any case, Robb's broken betrothal was not the sole cause of Red Wedding. By then, He had lost the North, his heirs and Karstarks. His fate was sealed and Lord Frey did not want to be on the losing side.