The appearance and behavior of notwithstanding are pretty odd—and they seem odder the more you look at the word. In the first place, withstand doesn't mean, as you might suppose from adding with to stand, "stand with," but rather "stand against." In this respect, the with- component functions like the with- in withdraw ("draw against") or in withhold ("hold against"), and not like the with- in withal ("together with").
The not- component makes sense in constructions of the type "Y is true, X notwithstanding," where we can infer that the sense is "Y is true, and under scrutiny X does not stand against it." But when we flip the construction around to say "Y is true, notwithstanding X," it is easy (albeit erroneous) to imagine that the statement logically means "Y is true, and under scrutiny it does not stand against X"—which doesn't make sense if X and Y tend in opposite directions.
What's going on here? Let's pick up the thread from Bryan Garner, Garner's Modern American Usage, third edition (2009):
notwithstanding is a FORMAL WORD, used in the sense "despite," "in spite of," or "although." E.g., "Notwithstanding an outpouring of editorial opinion on either side of this issue, there are no easy answers." [Citation omitted.]
The question that literalists ask [about notwithstanding] is, What doesn't withstand what else? Is the outpouring of opinion "not withstanding" (i.e., subordinated to) the lack of easy answers, or is the lack of easy answers "not withstanding" (subordinated to) the outpouring of editorial opinion? Because the former is the correct reading, some believe that notwithstanding should be sent to the end of the phrase in which it appears: The family's objection to the marriage notwithstanding, as opposed to Notwithstanding the family's objection to the marriage.
But the literalist argument is very much in vain, as the OED attests with a 14th-century example of notwithstanding as a sentence starter. This usage has been constant since from the 1300s to the present day. In fact, the construction with notwithstanding following the noun first appeared more than a century later, and has never been as frequent. ...
Ernest Weekley, An Etymological Dictionary of Modern English, volume 2 (1921), at page 993 of the book itself (but page 497 of the online viewer with the scroller at the bottom), offers this brief account:
notwithstanding. From not and withstand, to oppose, the word now app[ears] governed by the prep[osition] being really the subject of the verb, e.g. notwithstanding this is "this is not opposing." Cf. archaic F[rench] nonobstant, L[atin] non obstante (abl[ative] absolute).
[Early example:] Not that withstanding she ansuered in this manere
([cited in] N[ew] E[nglish] D[ictionary, Oxford, 1884] ca. 1500).
And finally, Wilfred Funk, Word Origins (1950) has this:
When a man finds himself faced with a lot of stubborn obstacles in some business project, he will occasionally make a decision that nevertheless and notwithstanding these handicaps he is still going ahead. At one time the word with meant "against," and so our entrepreneur is going to take his gamble notwithstanding, or, in other words, "no matter what stands against him."
So both "notwithstanding X" and "X notwithstanding" mean "in spite of X"; within that clause, notwithstanding is position-independent and aligns against X regardless of which element comes first in the clause. If that seems confusing, imagine how a person in medieval England would have felt if told by a dangerous-looking armed man, "You're either with us or against us!"