Just to clarify -- if one wronged another person, then one must apologize to them as part of teshuva. Consensual behavior, however, would not require their apology.
The answer is yes -- teshuva works. Rav Moshe Feinstein has a couple of responsa starting OC4:117 about teshuva for various intimate acts; the common theme to them is "yes it was a sin; you should regret it, stop doing it [and avoid situations where you're tempted or triggered], confess it to God, and commit to do better; maybe fast once a month for a few months and say some extra Psalms if you can. But any exaggerated language about automatically wiping out your soul, or worse than all other sins or whatnot -- aren't literal." Rambam's Laws of Teshuva, similarly, has a bunch of categories of sins and their punishments; none of this reincarnation and the like stuff. (He also acknowledges that some texts exaggerated the punishment for certain acts; they meant "if you do this habitually", not if it happened once and the person repented.)
I'd heard an Orthodox psychologist at an OU event mention a similar point -- a lot of people tell them they feel so guilty that they believe teshuva won't work; he points out to them that starts to sound like another religion. We have laws that we follow, and those include teshuva.
As discussed on a similar matter, while sincere regret is required, the goal needs to be to get more involved in Torah and mitzvos, not less; someone who is so paralyzed by guilt of their past that they don't go to synagogue, for example, is just compounding their problem.
Pischei Teshuva YD1:6 tells of a kosher butcher who wants to confess to a rabbi on his deathbed: Rabbi ... there was once a non-Jewish woman ... and unrelated to that ... I had a drinking problem; sometimes I was drunk when slaughtering animals and didn't use the right kosher technique. The rabbis agonize about that second half of the confession -- what do we now tell all the people who bought meat from this fellow, and are their dishes kosher? The first half of the confession gets no discussion at all.
(Don't get me wrong -- it is wrong and don't do it! But if someone sincerely repented about it, they have to move forward.)