There are three and a half different ways to use however*. This one needs a semicolon.
The first is using it as a conjunctive adverb. In this sense the meaning of however is that the independent clause that follows counters the independent clause before it (denying it, giving a caveat, stating something as true that we would not expect considering the first clause, etc.)
As a fully independent clause, it needs a semicolon to separate them. (As per the link MετάEd gave in the comment on the question, though note that a conjunctive adverb is not the same as a conjunction, so the "Don't use it with with conjunctions" doesn't apply).
And with conjunctive adverbs of more than one syllable, we use a comma after it to help clarify what is the second independent clause.
That's use of however number 1. Number 1½ is that since they're independent clauses we can just have them as separate sentences:
Our plane was delayed overnight. However, the airlines reimbursed us for lodging.
We would favour a new sentence or a semicolon depending on whether we wanted the semicolon's suggestion of a particularly strong tie between the two clauses.
(There are some who dislike starting a sentence with however so some style-guides prohibit it, but there's no grammatical reason not to, and it's as good an option to have available as any other. Most style-guides now allow it.)
We can use however as an aside, pointing out that the sentence (or possibly an independent or parenthetical clause, though as a matter of style that could get fiddly) opposes the previous:
It looks as though he's upset. She told me, however, that he always has that look on his face.
Here we use a comma both before and after.
Finally, we can use it to mean "to whatever extent or degree", "in whatever manner" or "by whatever means". This sense must not use a semicolon or a comma.
However we use punctuation, the goal is always clear expression.
This goal is shared by all writers however they decide to deal with those cases where different style-guides disagree.
If you don't use a semicolon in the cases in your question, you can end up using however in this sense, when you intend the conjunctive adverb sense:
Some sentences are ambiguous; however, we try hard to avoid this.
Some sentences are ambiguous however we try hard to avoid this.
The first sentence here states two separate thoughts, and points out that one is opposed to the other: "Some sentences are ambiguous" and "we try hard to avoid this".
The second sentence states that no matter how hard we try to avoid it, some sentences are ambiguous.
These two grammatically correct sentences differ only in whether we followed the semicolon-and-comma rule you mention, showing its value clearly.
*Four-and-a-half if we include the informal use as an emphatic form of how; "However did you manage that?". This comes from a sense where the original how + ever works, ("How ever did you manage that?") and many would say that this is the only correct form here, and however should not be used.
