YSK it's either "should have" or "should've". "Should of" is incorrect
Why YSK?
The first person who typed "should of" probably heard of it in real life that was meant to be "should've", they typed "should of" online and readers thought that it's grammatically correct to say "should of" which is in fact wrong and it became widespread throughout the years on Reddit.
While it is true that "should of" etc. can easily originate from a confusion between "'ve'" and unstressed "of", which sound identical, the statement
"Should of" is incorrect
itself is at least a bit misleading and prescriptivist in its generality.
Interestingly, there seem to be at least some native English speakers who genuinely do say "should of" (with a stressed "of") sometimes. This paper for example argues that people who say "should of" really do use a grammatical construction of the form modal verb + of + past participle. One argument the author mentions is that this would also explain the words "woulda", "coulda" and "shoulda", since "of"->"a" is quite common in general (e.g. "kind of" -> "kinda"), but "'ve"->"a" basically doesn't occur elsewhere (e.g. no one says "I'a" or "you'a" instead of "I've" or "you've"). Another is that the reverse mistake, i.e. using "'ve'" in place of "of" (e.g. "kind've"), is much rarer, which is a clear difference to e.g. the situation with "they're"/"their"/"there", where people use these words in place of the others in all combinations frequently. I recommend this blog article for a much longer discussion.
Also, whether genuine mistake (which it almost certainly is in many cases, although probably not all) or different grammatical construction, YSK that "should of" etc. didn't just become popular recently, but have been used for centuries. E.g. John Keats wrote in a letter in 1814: "Had I known of your illness I should not of written in such fiery phrase in my first Letter.". Many more examples (some older as well) can be found e.g. here or here.
TL;DR: While in many cases "should of" etc. can well be a mistake, originating from the fact that it sounds identical to "should've" when unstressed, there is some interesting linguistic evidence that at least in some dialects of English native speakers really do say "should of" etc. (i.e. in those cases it is not a mistake, merely non-standard/dialectal).
A common mistake is to write ‘could of’ instead of could have or could've
I could of told you that.
I could've told you that.
The reason for the mistake is that the pronunciation of ’ve is the same as that of of when it is not stressed. This is a common error but it is definitely considered wrong in standard English.
"Should of" is grammatically incorrect, regardless of whether the user/speaker is aware of its incorrectness. It's a fact, and a fact per se cannot be misleading. It's as simple as that. Linguistic conventions, as you've illustrated, can be formed over time, but that again doesn't take away from the fact that such usage is grammatically incorrect to begin with.
Just read the second (or the first, but that is more technical) link I shared. Some native speakers do in fact seem to say "should of" even when the "of" is stressed, so in their dialect it would be grammatical.
...the reason "in some dialects of English native speakers really do say 'should of' etc" is phonetics. Kids hear "should've" and repeat it phonetically, before learning the actual words or their meaning. Combine that with the awful state of education and literacy in the USA (and other countries etc) and voila, you've got some armchair internet expert justifying it with some big words trying a weeeee bit too hard to make it work.
Then you've got teachers who still gaf and know their shit who will correct this before middle/high school, and no, last I checked it was never added to the dictionary or considered correct. Language of course is living and ever changing, but the line must be drawn somewhere lest we devolve into shouting and grunts like neanderthals