In connection with the "American superfluous 'of' ", I always think of another similar mistake, "I should of done it that way". In the US we pronounce "have" in that position that way, but of course it must be spelled "have", not "of". But people who don't write well spell it the way they hear it (naturally enough), and then come across like pitiable ignorami, more's the pity.
I don't think the two "of"s are related, but I always think of them together.
"Should of" is just a misspelling of "should've"
There are a lot of cases like this. People hear "victual" and write it "vittle", hear "voila"" and write "wahla" or hear "teat" and write it "tit". If dictionaries are going to include that definition of "of", then they should define "teh" as a specific article.