Because tchrist's answer effectively covers the broader questions asked here, I want to focus on the specific phrase "turn up missing." That the expression has been around for the better part of two centuries is evident from this Ngram chart plotting the frequency of occurrence of "turn up missing" (blue line), "turns up missing" (red line), and "turned up missing" (green line) for the period 1800–2005:
This is not the chart of an expression that is heading toward eclipse.
Among the earliest notices of the expression in a reference work is this one in John Farmer, Americanisms—Old & New (1889), in an entry for missing:
MISSING. — AMONG THE MISSING.—Absent ; (and sometimes) killed. A quaint perversion of language characterizes a variant of this phrase — to turn up missing. [Relevant example:] Antonio was not only lazy but he was vicious, jealous, and in some of his mad moments he had often threatened to kill Marie. Finally Marie TURNED UP MISSING, and she was no longer seen about the cabin of the half-breed. — Missouri Republican, February 24, 1888
A Google Books search turns up an earliest confirmable match for the phrase from "European and North American Railroad," in American Railroad Journal (May 10, 1851):
He [John Howe, of the Government of Nova Scotia] pleads most eloquently the past loyalty of Nova Scotia, which, like a dutiful child, has received no rewards for good conduct, because in no danger of going astray ; while Canada, like the prodigal son, had received the fatted calf, though she had spent millions of the paternal estate in her riot-ous proceedings. He says that the loyalty of Nova Scotia has been without a flaw ; but intimates, that he will not promise that she may not be led to do something dreadful, unless properly restrained. That she cannot get on much longer in the old way—that something must be done, or all this loyalty may soon turn up missing. He tries in one part of his argument to convince Lord Grey that John Bull and Brother Jonathan never will set their horses together.
And from Philip Paxton, A Stray Yankee in Texas (1853):
Among the limited number of planters that then raised cotton, a little money was sometimes to be found, if their store bill did not overrun their crops ; but with the stock-raisers who occupied all the prairie-coast country, not one in ten could boast of a dollar. Their circulating medium possessed locomotive powers, and circulated upon its own legs. It consisted simply and solely of cows and calves. We have all heard of riches taking wings to themselves and flying away. Their wealth often walked off upon four feet, and when most needed, was very apt to turn up missing.
An Elephind search, meanwhile, turns up an even earlier instance from "California," in the [Houston] Telegraph and Texas Register (August 20, 1845):
We would advise Uncle Sam to take possession of the remainder of the Mexican territory, while it is yet time, to secure the payment of the indemnity due to American citizens. We say while it is yet time, because when once Great Britain has obtained a foothold, the limits of the Californias will not restrain her; nor will it be long before her philanthropic disposition will lead her to extend her protecting aegis over adjoining territories, and to thrust her blessings of civilization and "British liberty" down the throats of the semi-savage Indians of Mexico, even at the point of the bayonet[.] If a Mexican State or two were annexed to the United States every time an instalment of the indemnity turned up missing, it might at least have the good effect of inducing some exertions to meet the payments in future.
The earliest instance of "turn up missing" in a British Newspaper Archive search is from an unspecified item in the [Londonderry, Northern Ireland] Coleraine Chronicle (September 16, 1854) [combined snippets]:
On this occasion the ship displayed no light, and the superstitious fishermen imagined she might be one of Davy Jones fleet. Next morning Jemmy C. turned up missing, and the Petrel, (the name of the boat he had taken out to the ship,) was washed ashore, it was the general opinion he went to Davy Jones’ locker.
And the next earliest instance is from "Latest from America," evidently a letter or report from a correspondent in the United States, in the Sheffield [England] Independent (June 21, 1862) [combined snippets]:
We bear through a private channel in which we confide, that the which we confide, that the Unionists of Texas will soon be heard from. We understand that their arrangements for for restoring their State to the Union have been quietly matured, and that they have ere this thrown the old flag to the breeze, under the lead of General Sam. Houston. Though we wish the Kansas expedition southward, planned and organised last winter, had been prosecuted, we cherish strong hopes that the rebels of Texas will soon turn up missing, and that old Sam and Uncle Sam will have possession of the State. We await further tidings with lively interest.
Since a rash of instances of "turn up missing" turned up present in the middle 1850s (and continued thereafter) in the United States, it seems likely that John Farmer was correct in claiming that the expression was originally "an Americanism."
It is hard to say, however, whether the phrase's earliest users shared the OED's understanding of the phrasal verb "to turn up" as meaning "To appear or present itself in a specified character; to be found to be" (as cited in tchrist's answer) or whether they embraced its surface paradox (as I think Philip Paxton probably did) or whether they simply didn't notice the superficial contradiction at all.