The phrase "over the counter" in the context of retail transactions appears in English publications at least as early as the 1830s. For example, the phrase "all retail over the counter" appears seven times in the description of the action in Filmore v. Hood (November 21, 1838), a case in the Court of Common Pleas, reproduced in The [London, England] Law Journal Reports (1839), starting with this instance:
The declaration alleged, that the defendant entered into an agreement with one B. for the sale of a lease of a public house for a certain sum; and that, at and before and after the said agreement, the defendant falsely, fraudulently, and deceitfully pretended and represented to the said B, that the trade of the house had been, and then was, 180l. per month, all retail over the counter ; and the said B. not being able to complete the contract, it was agreed between the plaintiff, the defendant, and B, that the plaintiff should become the purchaser instead of B, and at and before the agreement, B. communicated to the plaintiff the statement and representation as to the value of the house, made by the defendant to him, of which the defendant had notice, and the plaintiff confiding in such representation, agreed to become the purchaser of the premises for a certain sum, which he paid to the defendant.
In this case, the phrase "all retail over the counter" seems to mean something like "all in the form of direct transactions between the host/server/seller behind the counter and retail customers on the other side of the counter." Implicit in this understanding of "over the counter" is the idea that it applies to discrete, ad hoc, relatively informal exchanges of goods or services for money between a seller and a buyer.
In the context of drugs and medicines, however, the phrase "over the counter" seems originally to have applied not to the place where the sale of the item occurred or to the nature of the medicine itself, but to the source of the prescription. That is, an "over-the-counter" prescription was one made by the chemist or apothecary on the premises, rather than by a trained physician in a medical office. Two early examples—one from England in 1865 and one from Australia in 1873—seem to support this understanding. From "The Twenty-fourth Anniversary Meeting of the Pharmaceutical Society," (May 17, 1865) in The Pharmaceutical Journal and Transactions (1865):
Mr. COLLINS (who came in late) said then he must not complain. He must say, however, that he thought the Medical Council had put forward a most extraordinary recommendation with regard to the Bill [the pending "Chemists and Druggists Act" updating the Pharmacy Act of 1852]. He hoped that those who had charge of the Bill would not allow such a monstrous clause to be inserted. He and many others had no desire to prescribe in the strict sense of the word over the counter ; but whilst medical men sent out medicine, he thought they ought not to object to chemists and druggists prescribing any simple remedy over the counter. If they dealt in those matters they knew the penalty which attached to it, and, should application be made to them, every sensible man, when he saw a case of difficulty, would advise the applicant to apply to a properly qualified man.
Mr. HILLS said that he had never heard it mentioned that the Medical Council wished to prevent Pharmaceutical Chemists from prescribing over the counter.
...
Mr. COLLINS said he thought there was something behind it, and asked for an explanation of what was meant by "any branch of medicine." Hi opinion was, that under that clause a chemist and druggist might be prevented from prescribing a simple chalk mixture, under the plea that he was practising a branch of medicine, and he called upon the Council to strongly oppose any restriction being placed upon their present liberty with regard to prescribing.
The bill in question evidently included language that might be interpreted as disallowing chemists and pharmacists to prescribe medications to their customers if such prescribing were viewed as "practising medicine":
An extract from the Minutes of the proceeding of the [Medical] Council (which will be found elsewhere in this Journal) sets forth the general view taken of Sir Fitzroy Kelly's Bill, and more particularly enters on this question of counter practice, proposing an addition to the 17th Section (which now declares that no provisions of the Act are in anywise to interfere with the vested interests of medial practitioners) of these words:—"or to entitle any person registered under this Act to practise Medicine or Surgery, or any branch of Medicine or Surgery."
Mr. Collins's concern appears to have been that the proposed wording might prohibit the common "counter practice" of a pharmacist's informally prescribing patent medicines or other common nostrums to customers without guidance from a certified "medical man."
And from "Women as Chemists," in the [Toowoomba, Queensland] Darling Downs Gazette and General Advertiser (February 5, 1873):
Of shops kept by druggists and chemists there are two kinds. Those who study the physiognomy of our streets must have observed that in poor and densely populated districts druggists shops spring up with amazing rapidity, and appear to meet with a tolerably uniform success. One which is at first represented by a few bottles, plasters, and half a dozen tooth-brushes, may be seen before long adorned with plate-glass, colored jars, &c. This is an "over-the-counter business." Proprietary or patent medicines, pills, plasters, horse medicine, rat poison, and specific remedies for every known disease are sold ; but the pennyworth or two-pennyworth of physics are paid for on the spot, and form the staple of the trade and profits. The men who keep these shops are often exceedingly ignorant : but they, nevertheless, prescribe largely for the poor, the advice being as it were thrown in gratuitously with the medicine, and paid for in ready money; it need hardly be said that young and needy medical men are in this way very heavily handicapped. But by the recent change in the law certain drugs may not be sold at these shops, nor may the owners assume that title of pharmaceutical chemists. The other class is that presided over by those who pass the prescribed examination of the Pharmaceutical Society, and is chiefly employed in compounding and dispensing the prescriptions ordered by medical men. To these persons certain privileges are secured, and they are legally entitled to announce themselves as pharmaceutical chemists.
Here, again, we see "over-the-counter" prescriptions contrasted with medical prescriptions. In my Google Books and Elephind database searches, instances of "over the counter" as a description of pharmacists' prescriptions were more frequent (until the 1910s) than instances of "over the counter" as a description of specific classes of medicines.
Missing from either of these early accounts is any mention of instances in which customers march into a pharmacy and summarily demand a bottle of Aunt Granny's Bitter Bristle Root for what ails them. Such self-directed prescriptions—based on personal experience, informal advice from friends and relatives, or recommendations appearing in TV commercials—may well account for most "over-the-counter" drug sales today. Nevertheless, some customers still undoubtedly ask the counter clerk at CVS for advice about which preparation they should buy to treat a particular ailment, thereby summoning the old form of "over-the-counter prescription."
Conclusions (added on December 4, 2022)
My answer attempts to distinguish between "prescribing over the counter" and "selling over the counter." The goal of the proposed Chemists and Druggists Act of 1865 was evidently not to forbid pharmacists to sell potentially hazardous drugs over the counter to a customer who had received a prescription for them from a qualified physician, but rather to forbid pharmacists to prescribe such drugs—or to recommend other treatments in a manner that amounted to "practising medicine"—over the counter. The actual sale—the physical exchange of money for drugs "over the counter"—would of course be the same, regardless of the source of the prescription.
I see a fundamental distinction between (on the one hand) drugs prescribed in a medical office or at a patient's home by a doctor but sold over the counter by a pharmacist and (on the other hand) drugs prescribed by a pharmacist in a pharmacy and sold over the counter by that pharmacist. The latter, I think, is what Mr. Collins has in mind in talking about prescribing over the counter. He further tries to distinguish between "prescribing any simple remedy over the counter" and prescribing treatments requiring professional medical expertise over the counter—what he calls "to prescribe in the strict sense of the word over the counter."
The acceptable subset of "simple remedy" treatments that (according to Mr. Collins) ought to be within a pharmacist's rights to prescribe "over the counter" may well have included, in 1865, any number of simple drugs that were not prepackaged for off-the-shelf purchase. Over time, however, as prepackaged drugs and other medicines became the norm for "simple remedies," the term "over the counter" seems to have migrated from the prescription to the prepackaged product itself.
Even so, the old distinction between "prescribing by a physician" and "prescribing over the counter [by a pharmacist]" might help explain why people today divide pharmaceutical drugs into "over-the-counter drugs" (those that can be purchased off the shelf, without a doctor's prescription) and "prescription drugs" (those that must be specially bottled by the pharmacist and sold only to buyers who have a doctor's prescription for them), despite the fact that the pharmacist ultimately sells both types of drugs to customers over a counter.