You asked why people who "believe in" avoiding nonmarital sex so frequently engage in and report badly regretting it. Instead of responding within your frame, I'm going to lay out the interpretive framework that seems most natural to me to use for this problem, and then answer in those terms.
We can call things or actions good or bad, right or wrong, with reference to some intention that both the speaker and listener have in mind. For instance, a sturdier and sharper knife is a better one, because our uses for knives tend to converge. We can expect to be understood when we call some knives "good" and leave out "for cutting," and likewise when we call spoiled food bad without reference to a shared interest, because it harms the body of the eater, which harm we generally expect animals to try to avoid.
Moral injunctions such as "it is wrong to lie," "it is bad to steal," can diverge from the local interests of the organism being admonished, in service of a larger, convergent goal. By abstaining from some narrowly self-interested behaviors now, we preserve the necessary conditions for our needs to be met in the future, and the relation between the costs and the benefits can in principle be explained within the system of reference that judges actions as good or bad.
Not all injunctions are like this. For instance, reproduction is such a large component of inclusive fitness that it's not clear what good an organism could get to compensate it for forgoing reproduction. If, like the early Essenes or Christians, we judge sexual desire and activity to be simply bad, we cannot explain this inside the moral system in terms of an animal's rational decision to defer gratification. (This isn't an analytically certain proof, and depends on some contingent facts about apes. If ants or bees talked about something like right and wrong, or good and bad, their relation to those ideas might work very differently from ours.) Instead, we have to explain these statements from an independent system of reference, outside the one that judges reproduction to be bad. There are two things to be explained:
1 How can someone be induced to persistently endorse, promote, and act on perverted moral judgments, i.e. judgments that on net oppose rather than promote their interests as an organism?
2 How are such inducements ecologically fit? Why are they selected for and under what circumstances? Why do we see a lot of them, with lots of discernible traces in the world, rather than a negligible amount?
In some primate groups, a dominant male will punish submissive males for revealing sexual desire for the sexually mature females. This is not exclusive to language-using apes, so it cannot be a mere instruction to lie - it has to be a demand to fake disinterest, i.e. to distort one's own behavior to emulate it. This is an easy to understand example of an important general fact about humans: we can be threatened into internalized preference falsification, i.e. preference inversion.
There seems to be some sexual heterogeneity here. On priors this makes sense; while women's concealed estrus allows them to consciously decide whether to conceal or reveal sexual interest, men's erections are notoriously difficult to control consciously, so adolescent men rapidly learn to deform their unconscious desires to match what their society says they ought to want. Experimental evidence confirms this; while both women and men will predominantly tend to report sexual arousal patterns that conform to social desirability, men's genital arousal patterns conform to their constructed identities much more than women's do.
Ecologically, preference inversion seems likely to persist if groups using that social technology have an advantage in recruiting their members into conflicts against other groups, and thus in winning those conflicts. This can take the form of warfighting at scale, which requires people to move towards danger with no clear self-interest in doing so. It can also take subtler forms of indirect conflict, of the sort described in The Debtors' Revolt, Moral Mazes, The Golden Notebook, The Fountainhead, etc.
The ecological success of moral perversions depends on their uneven adoption, i.e. on hypocrisy. If everyone felt an uncomplicated preference for moving towards danger, there would not be a next generation. Likewise if everyone were chaste and celibate. Submissive males in a primate group will be hoping for opportunities to supplant the dominant male, or to subvert his control. Clerics and warriors are recruited or retained through enjoying more approval than peasants for the "virtues" of asceticism and danger-seeking, but they survive through the fruits of peasants' "vicious" way of life, and in some cases have to replenish their own population by recruiting from "bad" peasants.
To generalize, if you have been coerced into participating in a perverted moral order, you are stuck with some combination of internalizing an orientation against life, and internalizing an orientation against morality, i.e. being "bad." A priest or warrior might imagine that they are possessed by a god when lying to peasants or murdering enemies, but possessed by some demon when seeking forbidden intimacy or abandoning a fight. In Freudian terms, these correspond to the superego (literally "above-me," the imagined authority to which you attribute agency for your destructive behavior) and the id (literally "it," an imagined subversive subagent with all the desires your moral frame demands that you disown).
One thing that can cause confusion here - by design - is that perverted moralities are stabler if they also enjoin nonperversely good behaviors in most cases. This causes people to attribute the good behavior to the system of threats used to enforce preference inversion, imagining that they would not be naturally inclined to love their neighbor, work diligently for things they want, and rest sometimes. Likewise, perverted moralities also forbid many genuinely bad behaviors, which primes people who must do something harmless but forbidden to accompany it with needlessly harmful forbidden behaviors, because that's what they've been taught to expect of themselves.
Some societies have norms against nonmarital sex that really do seem to function to promote marital intimacy and monogamous household formation - notably, the Amish and non-Modern Orthodox Jews. There also seems to be a less legibly distinct subset of more conventional conservative Christians who report being eager to marry and experience marital intimacy, though I am not sure how they reconcile this if at all with the New Testament. But these are not the people you are asking about.
You are asking about people whose relevant narrative center is not the positive value of marital intimacy, but the badness of sexuality, whether or not they mouth a party line endorsing the former. Many people in these types of conservative Christian cultures - more often women in my experience - report that after marriage, they have difficulty engaging in sexual behaviors, because they've learnt from childhood that sex was bad and dirty, and it's confusing for this behavior to suddenly shift from condemned to endorsed.
At this point the behavior you describe should no longer be perplexing. People who have been coerced into preference inversion cannot honestly report their own preferences or intentions as an organism. Instead, they must choose between some combination of internalized coercion, and complementary demonic possession.
This treatment of the topic is very compact. I was heavily influenced by Jessica Taylor's On Commitments to Anti-Normativity, and Friedrich Nietzsche's Genealogy of Morals.