Christine Ammer, The Facts on File Dictionary of Clichés, second edition (2006) has this entry for the phrase "not until the cows come home":
not until the cows come home Not for a long time. Presumably the time referred to is when cows return to the barn for milking. The term has been around since the late sixteenth century. Beaumont and Fletcher's play The Scornful Lady (1610) stated, "Kiss till the cow come home."
Robert Allen, Allen's Dictionary of English Phrases (2008), who also cites The Scornful Lady, concurs with Ammer as to the original sense of the phrase:
till the cows come home
for ever, indefinitely: from the former practice of leaving cows out at pasture until they were ready for milking. 16th cent
Early usage in England
Here is the quotation from The Scornful Lady with a bit more of the surrounding play for context:
Enter young Loveless, and his Comrades, with Wenches, and two Fidlers.
Young Loveless. Come my brave Man of War, trace out thy darling,/And you my learned Council, sit and turn Boys,/Kiss till the Cow come home, kiss close, kiss close Knaves./My Modern Poet, thou shalt kiss in Couplets./ Enter with Wine. /Strike up you merry Varlets, and leave your peeping, This is no pay for Fidlers.
Like Ammer and Allen, William Carew Hazlitt, English Proverbs and Proverbial Phrase Collected from the Most Authentic Sources (1907) cites the occurrence in The Scornful Lady (albeit with a later publication date, but Hazlitt presents the proverbial phrase itself as including the word kiss:
Kiss till the cow come home
This appears to be introduced proverbially into Fletcher's Scornful Lady, 1616, where Loveless says: "And you, my learned council, set and turn, boys;/Kiss till the cow come home." [Citation omitted.]
However, Hazlitt fails to note that Beaumont and Fletcher used "till the cow come home" in another play—The Captain (circa 1609–1612)—in the context of drinking rather than kissing:
Host. Good night!
Jacomo. Good morrow! Drink till the cow come home, 'tis all paid boys.
George Apperson, The Wordsworth Dictionary of Proverbs (1993), which I believe is a reprint of Apperson's English Proverbs and Proverbial Sayings: A Historical Dictionary (1929) gives an instance of "till the cow come home" from Alexander Cooke, "Pope Joan: A Dialogue Between a Protestant and a Papist" (1625), reprinted in The Harleian Miscellany (1745):
And when he is made one [a priest], and hath gotten a Benefice, he consorts with his Neighbour Priests, who are altogether given to Pleasures ; and then both he, and they, live, not like Christians, but like Epicures; drinking, eating, feasting, and revelling, till the Cow come Home, as the Saying is ; playing at Tables, and at Stool-ball ; and, when they are well crammed and tippled, then they fall by the Ears together, whooping, and yelling, and swearing damnably, by God and all the Saints in Heaven.
and a first occurrence of the modern form "till the cows come home" from Swift, Polite Conversation, Dialogue II (1738):
Miss Notable. I suppose, my lord, you lay longest abed today?
Lord Smart. Miss, if I had said so, I should have told a fib; I warrant you lay abed till the cows came home: but, miss, shall I cut you a little crust, now my hand is in?
Miss Notable. If you please, my lord, a bit of undercrust.
Usage in the United States
In a Google Books search for the phrase, "till the cows come home," the earliest match appears in the context of an extended example of "The Yankee Dialect" in a handbook titled How to Talk (1857):
He [the Yankee] says I guess when he means I think ; uses the word awful in the sense of ugly and very great ; ary for either ; back and forth for back and forward ; blows up his help instead of scolding them ; swaps jack-knives and horses ; is seldom green enough to get into a fix ; generally goes the whole figure, and holds on "till the cows come home ;" but occasionally his enterprises fizzle out, and he is obliged to fork over the dimes and back out, or be smashed up.
By "Yankee," the anonymous author of this handbook seems to mean "New Englander," since he addresses "The New York Dialect" in a separate section.
Other examples soon follow. From a letter dated September 23, 1858, and included in Life and Correspondence of Theodore Parker: Minister of the Twenty-eighth Congregational Society, Boston, volume 2 (1864):
Massachusetts is likely to send a stronger anti-slavery delegation to Congress than ever before. ... Governor Banks would, no doubt, lower the Republican platform, if that operation would help him up. But Massachusetts will oppose any such act, so will the people of the North. If we put up a spooney, we shall lose the battle, lose our honor, and be demoralized. Edward Everett is beating every New England bush for voters to elect him. He may beat till the cows come home, and get little from his labor.
And from Gail Hamilton, "The Pursuit of Knowledge under Difficulties," in Atlantic Monthly (March 1860):
"But do consider, Mr. Geer, the child has got to leave us some time. We can't have her always."
"Why can't we?" exclaimed Mr. Geer, almost fiercely.
"Sure enough! Why can't we? There a'n't nobody besides you and me, I suppose that thinks she's pairk. What's John Herricks and Dan Norris hangin' round for all the time?"
"And they may hang round till the cows come home! Nary hair of Ivy's head shall they touch,—nary one on 'em!"
(I have no idea what pairk means in the above quotation.)
Conclusions
The earliest form of the expression seems to have been "till the cow come home" from the late 1500s or early 1600s, with "till the cows come home" in use by 1738. The references I consulted agreed that the expression refers to cows coming back to the barn from the pasture either in the evening or in the morning, not to cows escaping the confines of a farm and not returning at all. Indeed, Eric Partridge, in his edition of Swift's Polite Conversation [combined snippets], says that the original phrase had the sense "till the cow come home for milking"":
'lay a Bed 'till the Cows come home': the unit is 'til(l) the cows come home, earliest (1610) till the cow come home (for milking).
Update (May 23, 2021): Even earlier instances of 'till the cow come home'
It now appears that Beaumont and Fletcher were not the first authors to commit "till the cow come home" to paper. A search of Early English Books Online yields two examples from before 1600 and another from 1610—the same year as The Scornful Lady.
From John Prime, An Exposition, and Observations upon Saint Paul to the Galathians togither with Incident Quæstions Debated, and Motiues Remoued (1587):
I knowe the world is cunning, and can distinguish, and iangle of tithes and church-liuings too and fro, till the cow come home, and that in some is borne withal, which in some others is sacrilege without any alteration of other circumstance, but that affection can winke when it will. When all is done, for I purpose not to enter particular discourse thereof, the resolution of all in all is, God wil not be mocked.
From John Eliot, Ortho-epia Gallica Eliots Fruits for the French: Enterlaced with a Double New Inuention, Which Teacheth to Speake Truely, Speedily and Volubly the French-Tongue (1593):
Well, shall we too it [playing a game of cards] now?
But thou Lancelot, so soone as thou hast gotten sixpence, you do giue them ouer, with whom you play.
That is rather to deceaue and mocke, then to play.
You say true indeed: For if I loose once sixpence, I am tied by the foote till the Cow come home.
And from Alexander Cooke, Pope Ioane A Dialogue Betweene a Protestant and a Papist. Manifestly Prouing, That a Woman Called Ioane was Pope of Rome: Against the Surmises and Obiections Made to the Contrarie, by Robert Bellarmine and Cæsar Baronius Cardinals: Florimondus Ræmondus, N.D. and Other Popish Writers, Impudently Denying the Same (1610):
PROTESTANT. ... If there be any lasie fellow, any that cannot away with worke, any that would wallow in pleasures, he is hastie to be priested. And when he is made one, and hath gotten a benefice, he consorts with his neighbour Priests, who are altogether giuen to pleasures: and then both he, and they, liue, not like Christians, but like Epicures: drinking, eating, feasting, and reuelling, til the cow come home, as the saying is; playing at tables, and at stoole-ball: and when they are well cramd, and tipled, then they fall by the eares together, whooping, and yelling, and swearing damnably, by God and all the Saints in heauen. And after all matters be somewhat pacified, then arising out of their whores laps they go to the Masse.
The instances cited here from 1587 and 1593 use the expression in settings where there is no reason to bring up a cow except to invoke it as part of a figurative phrase. And the instance from 1610 explicitly characterizes "til the cow come home" as a "saying."
