What are these seemingly incorrect sentences called?

Solution 1:

As far as I know (my grammatical knowledge is not extensive), these sentences are referred to as minor sentences. As Wikipedia states:

A major sentence is a regular sentence; it has a subject and a predicate, e.g. "I have a ball.". In this sentence, one can change the persons, e.g. "We have a ball.". However, a minor sentence is an irregular type of sentence that does not contain a main clause, e.g. "Mary!", "Precisely so.", "Next Tuesday evening after it gets dark.".

Other examples of minor sentences are headings (e.g. the heading of this entry), stereotyped expressions ("Hello!"), emotional expressions ("Wow!"), proverbs, etc. These can also include nominal sentences like "The more, the merrier".

These mostly omit a main verb for the sake of conciseness, but may also do so in order to intensify the meaning around the nouns.

The final, italicised part of the quote should answer your second question of the purpose of these sentences.

Solution 2:

"Computer grammar checkers often highlight incomplete sentences. If the context is clear from the rest of the paragraph, however, an incomplete sentence may be considered perfectly acceptable English."

https://en.wikipedia.org/wiki/Sentence_clause_structure#Incomplete_sentence

These are good examples of when the meaning is clear despite the lack of a verb.

They work because they are terse and concise; the addition of a verb would make them less so.

Solution 3:

Everyone else has adequately explained what is going on and why and how this structure is used, but have gotten the name wrong.

These are called Nominal Sentences:

Nominal sentence is a linguistic term that refers to a nonverbal sentence (i.e. a sentence without a finite verb). As a nominal sentence does not have a verbal predicate, it may contain a nominal predicate, an adjectival predicate, an adverbial predicate or even a prepositional predicate.

(Wikipedia)

The examples are in line with the ones in other answers:

Nominal sentences in English are relatively uncommon, but may be found in non-finite embedded clauses such as the one in, "I consider John intelligent," where to be is omitted from John to be intelligent.

They can also be found in newspaper headlines, such as "Jones Winner" where the intended meaning is with the copular verb, "Jones is the Winner".

Other examples are proverbs ("More haste, less speed"); requests ("Scalpel!"); and statements of existence ("Fire in the hole!"), which are often warnings.

A sentence such as "What a great day today!" is for example considered nominal because it doesn't have a verb.

(Wikipedia)

Solution 4:

A rather specific (and to me quite annoying) situation in which this structure is used is in sponsor announcements on radio and TV.

It takes the form of a voice announcing

"This program, brought to you by Joe Bloggs Yoghurt Farms."

I've always assumed that they use this form so the same announcement can be broadcast after the relevant item, as well as before it and during it. If they included the verb, they'd either have to record two versions ("this program is brought to you" and "this program was brought to you"), or have a slightly awkward-sounding "is brought to you" after the item has just finished.

I think it's the cheapskatery that annoys me.