"Linkspam", i.e. companies inserting promotional links, was a problem from the very beginning. And from the beginning, Wikipedians handled the issue very inconsistently.
Ironically, the first known instance of an offer to edit Wikipedia for pay came from Erik Moeller, on his userpage, on 24 May 2003. At that same time, Axel Boldt attempted to create a WikiMoney system, to use in bartering with other Wikipedians for mutual editing assistance. It failed to catch on. Moeller also openly encouraged the establishment of a bounty system.
On 20 July 2003 the page on 'Criticism of Wikipedia' argued that promotional editing or advertising would not be a problem for the Wikipedia model. "What about advertisers? Won't those with a product or service to hawk see the opportunity to hit a targetted market write new wikis for their product or worse, edit the wiki that corresponds to their generic product class (e.g. computer) to an ad for their product?" S/he argued that it could simply be treated as vandalism and simply reverted to its previous state.
A comment on the problem of 'spam', i.e. the insertion of promotional material or links appeared as early as August 2003. "Wikipedia faces an increasing challenge from spam: commercially-motivated entries, or whole articles, from for-profit companies or groups that promote a particular technology or business style."
The page also noted that Wikipedia was unlikely to be the target of spammers, because Wikipedia was not widely used, and its audience was limited to technically minded readers.
"Spammers must consider their audience (to a degree, anyway). USENET and email are general modes of communication used by a great many people, not all of whom are technically inclined. By contrast, the Wikipedia is an encyclopedia used by far fewer people, many of who are technically inclined - making it a far less attractive target".
March 2004: an editor explicitly encourages a corporation to edit its own Wikipedia article. Said editor is not punished in any way. And that is exactly what MathWorks did, using the IP address 220.127.116.11.
The first version of the COI page was created 11:11, 3 May 2004. It was mainly about ‘vanity pages’. “A vanity page is a sort of page created by a Wikipedia user, usually about himself or his associates, afflicted with many problems”.
March 2005: Greg Kohs, the most hated man on Wikipedia, starts editing. See below.
February 2006: a scandal erupts over Congressional staffers editing the Wikipedia articles about House and Senate members to make them more "benign", or in some cases to mock them. 
The wide world of Wikipedia, and why PR practitioners should take note - article published in March 2006 by the Public Relations Society of America. "Wikipedia seems to be the buzzword of the moment in electronic media circles. A Google search for the term turns up a staggering 196 million references. Yet many communications professionals don’t understand what it is and why they should care about it. Here are 10 guidelines to consider if you plan to contribute to Wikipedia on behalf of your organization or client."
Wikipedia:Editing with a conflict of interest was created 05:32, 10 August 2006 “If you are getting paid to write articles for Wikipedia, or if the subject of the article is very close to your profession, we encourage you to submit articles for community review, and letting a community member post them”.
"GraalOnline" was an early example of game promoters using Wikipedia to advertise product. See this AfD from August 2006. The article was deleted. "Comment as Nominator: The reason that I nominated this, as well as the above reasons, was that I believe that this article is unfixable. Because of GraalOnline's staunch opposition (harrsasing (sic) phone calls to Wikimedia Corp, which Brad Patrick described to me as: "That's how [this issue] was brought to my attention, that and the harassing phone calls from the crazy Frenchman.") to anything added which doesn't have a positive connotation and serve as an advertisment (sic), there will never be a NPOV on this page, unless GraalOnline corporation members are prevented from removing material. I would accept this resolution (GO staff being banned from removing material) as an alternate to deleting it, but if that isn't possible, delete it will be. Killfest2—Daniel.Bryant 07:12, 1 August 2006 (UTC)"
Also in late 2006, the Arch Coal article became a minor scandal.  "In addition to blocking the account, Wales deleted two articles produced by MyWikiBiz that Kohs had mentioned in his reply. However, one of the articles deleted, Arch Coal, had been copied from MyWikiBiz.com by another editor. This led the issue to come up for deletion review. Wales agreed that the discussion could proceed, although he called the article "a travesty of NPOV." The article was ultimately kept after a ground-up rewrite. Meanwhile, several more of the articles posted on MyWikiBiz.com were copied over by other editors after the situation flared up again." A lengthy discussion of it on the "Deletion Review" noticeboard was deleted, to hide something. The article was recreated and more argument ensued in 2008.
Arguments about paid editors became noticeable after the modern COI Noticeboard was created at the end of 2006 (shortly after the conflict of interest policy was created -- by Erik Moeller, disturbingly enough). As of late 2013, the COI Noticeboard was up to 62 archives, most 256k bytes long. By 2016 it was up to 100 archives, and still growing.
November 2006:  "It turns out that Wales read a “Tactics” article titled, “The wide world of Wikipedia, and why PR practitioners should take note.” Tactics is a monthly publication of PRSA. In response, Wales contacted Elsasser in November, saying the article was, “alarmingly wrong and advocates deeply unethical behavior.” The article talked about transparency and neutrality in edits. But as many of you may know, Wales deeply opposes any public relations professional or special interest directly editing Wikipedia articles. Wales' message continues to be “hands off Wikipedia” and he recommends that PR practitioners use the discussion page to add comment and concerns. "I did this just today, and you can read it on the Wikipedia page about mobile homes and watch how the community will respond, if it does at all (we’ll see). I think my comment was respectful and factual, plus it’s a subject I know well since I worked for the Manufactured Housing Institute for years, served as a trade editor on the subject and still do some work for the industry. However, I wasn’t on the payroll to make the comment.""
January 2007: Microsoft was "busted" for offering to pay editors to make Microsoft-related articles more favorable.   Jelliffe was attacked, simply for entertaining the idea. "Since you openly admit to being paid my Microsoft you immediately destroy any credibility as a neutral commentator. End of story. Ian Lynch | January 22, 2007 10:31 AM " (sic)
March 2007: Michael Snow writes a Signpost article claiming that a diploma mill called Almeda University was offering $50 to Wikipedia editors, to "clean up" Almeda's Wikipedia article. Predictably, numerous Wikipedians started editing the Almeda article, making it as negative in tone as possible. Also predictably, Ellen Smith later showed up to watch it, and insure it remained negative. The article's talkpage, with commentary running from January 2007 to October 2012, is a perfect encapsulation of Wikipedians attempting to defame someone or something they hated.
August 2007: the arrival of Virgil Griffith's Wikiscanner tool. "The result: A database of 34.4 million edits, performed by 2.6 million organizations or individuals ranging from the CIA to Microsoft to Congressional offices, now linked to the edits they or someone at their organization's net address has made. Some of this appears to be transparently self-interested, either adding positive, press release-like material to entries, or deleting whole swaths of critical material. "
For many years, discovery of paid editors resulted in hysterical attacks like this one, from September 2007. Note the comparison to Gregory Kohs's MyWikiBiz, noted below. Kohs was already their Public Enemy No. 1.
The first major arguments over a paid-editing policy occurred in 2009, leading to this list of failed proposals.
An RFC in June 2009 attempted to settle the question of the propriety of paid editing, with little result.
Also in June 2009, it was revealed that Wikipedia arbitrator David Boothroyd, editing under the name "Sam Blacketer", was actually a Labour Party operative who had been defaming Conservative politicians via their Wikipedia articles. Boothroyd resigned from Arbcom in shame. He already had a reputation for sockpuppeting, and two of his socks became administrators.
"Nearly one in six MPs have had their online Wikipedia entries changed from Parliament and dozens of the alterations appear to be attempts to erase embarrassing or disputed allegations made during the 2009 expenses scandal." This story was not widely reported until 2012, long after the fact. 
June 2011: Rauan Kenzhekhanuly and his group, WikiBilim, quietly makes major expansions of the moribund Kazakh-language Wikipedia, then starts editing English Wikipedia articles to make Kazakh subjects look better--most especially, Kazakh dictator Nursultan Nazarbayev and his family. It is not revealed until December 2012 that WikiBilim was being paid by the Kazakh government, as well as receiving financial assistance from the Wikimedia Foundation.
September 2011: Johann Hari.
December 2011: Bell Pottinger affair.
January 2012: PR expert Phil Gomes blogs about the difficulties paid editors have on Wikipedia. This leads to the formation of CREWE.
This article was created February 2012 and authored almost entirely by administrator Jake Orlowitz aka "Ocaasi", a member of Wikiproject Medicine who had a reputation for blocking paid editors, right or wrong. (Ironically, Orlowitz has worked very closely for years with Dr. James Heilman.) The article was originally posted under the Wikiproject for "Cooperation", was repeatedly moved, renamed and vandalized, and is still poorly written and organized. Even more ironic that the first major conflict of interest named was committed by Jimmy Wales himself in 2005, on his own biography (removing the contributions of Larry Sanger).
Ocaasi also created the article about CREWE at the same time. It was subjected to a very hostile AFD in March, after Wales attempted to delete it in violation of procedure:
"Comment - Whomever attempted deletion this for A7 should be sanctioned or de-sysopped, in my opinion. This seems to have been a flagrant WP:IDONTLIKEIT violation of Wikipedia policy, nothing this deeply fleshed out and so patently obviously relevant should be murdered in the night like a thief. PROD would have been declined at once, let alone speedy. Kudos to the administrator who overturned this rogue action. This is going to be a news story in the MSM that reflects poorly upon the project, I'm sure... Policies and guidelines apply to EVERYONE. Carrite (talk) 16:19, 12 March 2012 (UTC)"
"Well...Jimbo did it. :/ SilverserenC 16:20, 12 March 2012 (UTC)"
Ocaasi also maintains this list of paid editors. He routinely chases editors and accuses them of being sockpuppets run by one of these firms.
May 2012: An interview with Gomes appears on the Signpost. Result: angry spluttering, principally by David Gerard.
July 2012: CREWE attempted to open a "suggestion box" for paid editing discussion. It was deleted. Originally created by Eclipsed (T-C-F-R-B), see below.
September 2012: GibraltarPedia.
December 2012: The Kazakh Wikipedia/WikiBilim scandal draws Jimmy Wales into its orbit.
February 2013: Qorvis, one of the public-relations firms involved with Kazakh Wikipedia, Bell Pottinger affair, and similar paid-editing scandals involving corrupt dictatorships, tries to correct its own Wikipedia article. The writer creates an account, and edits no Wikipedia articles. He simply states he is available for reference help for anyone wanting to correct the article. Whereupon he is permanently banned, and loudly accused of "using an open proxy" and "sockpuppeting". He then blogs about it.
In fact, the article quite neatly gets to the crux of the problem with paid editing.
"I suppose Wikipedia is allowed to do whatever it wants. Yet, the problem is that Wikipedia has become the go-to encyclopedia. Wikipedia articles are at the top of internet search results. Wikipedia articles are used by children to write school papers. Wikipedia articles have even been cited by newspapers, such as the Seattle Times or Arizona Republic. Wikipedia thus has a responsibility to find an avenue for living subjects to contribute directly to the articles. It is a disservice to the public to not allow direct, transparent contributions by primary sources—especially since these sources often hide their identities in an effort to have their arguments heard."
"Though Wikipedia has such potential, it makes me long for the days of Encyclopedia Britannica’s fact checkers. Many Wikipedians do a wonderful job— but we must get beyond the rumors of Twitter, and newsrooms in the basements of too many 40-year-old stay-at-home sons for Wikipedia to become a first-rate dependable reference site".
"Matt J. Lauer is the president of Qorvis Geopolitical Solutions and a partner of Qorvis Communications, LLC."
One result: this insipid Twitter exchange.
"11:16 AM - 5 Mar 2013 Matt J. Lauer @MattJLauer
"We dont want to subversion offers. We want to be allowed open debate. @Qorvis @jimmy_wales 
"11:35 AM - 5 Mar 2013 Jimmy Wales @jimmy_wales @MattJLauer @qorvdis
"Your complaints are deeply dishonest to the point of being embarrassing. Your clients should fire you for it.
"11:35 AM - 5 Mar 2013 Matt J. Lauer @MattJLauer
"@jimmy_wales we just want a debate and to be able to edit under our name.
"1:47 PM - 5 Mar 2013 Jimmy Wales @jimmy_wales
"@MattJLauer Register as "Matt J Lauer". Post on your user page who you are. Have the debate. Stop pretending that's not allowed.
"1:51 PM - 5 Mar 2013 Matt J. Lauer @MattJLauer 5 Mar 2013
"@jimmy_wales All of us who have an interest Wikipedia @Qorvis, will register under our names if you unblock our qorvisnet or open proxy
"1:54 PM - 5 Mar 2013 Jimmy Wales @jimmy_wales 5 Mar 2013
"@MattJLauer @qorvis Send me an email. You'll need to apologize publicly and stop using fake accounts (sockpuppets).
July 2013: an SEO article openly advocates using Wikipedia articles for SEO purposes. "It’s also still worth pursing Wikipedia links when appropriate. Wikipedia is very picky about their references, so you’ll have to provide very niche, unique content, but if you can get a link it can bring about some pretty cool results – including other do follow links."
November 2013: more revelations of U.S. Congress people editing biographies. 
June 2015: PR firm Sunshine Sachs was accused of performing "purification" of biographies of its famous and wealthy clients. The edits were revealed by the WikiStrategies firm, co-founded by longtime Wikipedia insider Pete Forsyth. A clear example of public Wiki-backstabbing.  Little media coverage was given to this affair, although it was added to the Wikipedia article about the PR firm's founder Ken Sunshine. Both Forsyth and infamous paid-editing hater Coretheapple spent a great deal of time adding this material to Sunshine's article, which was clearly the work of paid editors in 2006, and was subjected to one AFD that failed.
January 2017: Greg Kohs makes a legal threat against Mark Devlin, operator of news website Newslines, who had already gained some infamy as a "Wikipedia critic". Devlin remarked that Kohs's website MyWikiBiz might be violating Wikipedia's "Terms Of Service". Kohs threatened a libel claim (basically an empty threat). Yet it led directly to a furious exchange on Jimbo's talkpage claiming that Kohs's website had been violating Wikipedia's TOS for years with "impunity". 
"He said this, even after Wales states the WMF requires a degree of proof which is higher than the community, so Jytdog must be confident it exists, or otherwise he has just driven a bus right through Kohs' BLP 'rights', and would be sitting out a block as we speak (indeed, with his record, it would quite likely be ban). The fact is, we all know the proof is easy to construct - it's the text of the ToU, it's Kohs' public statement he is still profiting from Wikipedia, and it's the lack of any compliant declaration by Kohs or any of his agents."
Among the squabblers: those magical Wikipedians Guy Chapman and Smallbones.