Older Than They Think: Russian author Alexander Pushkin's verse novel Eugene Onegin (published in serial form in the early 1800s) attracted quite a bit of this. What's more notable is that the author actively took part. At one point, he asked a group of fangirls where they saw the various ships of the novel going. When he didn't like their answers, he then lectured them on why their favored ships were wrong. Granted, he had a good point, since the shippers' preferred ships were incompatible with the book's aesop, but most people reading Eugene Onegin in serial form probably weren't aware there was a deeper literary point to the shipping drama.
Harry Potter's is probably the biggest and one of the first to take place in the virtual world of the internet. Even Rowling described it as akin to trench warfare. It can happen between any ship, though the largest and bloodiest (virtually, of course) was between the Ron/Hermione and Harry/Ginny ships vs. the Harry/Hermione ship, for obvious reasons. Though true shippers tended to stay with their own ship (because it's much more fun to talk with people who agree with you, than fight with people who don't), there were obnoxious militant fans on both side with a tendency to enter chat rooms or forums and spam them. There were also very vigorous debate threads on many of the main fansites. The war was exacerbated after the release of Half-Blood Prince and the infamous interview Rowling gave in which the interviewer suggested that any leftover Harry/Hermione fans were "delusional." Rowling agreed that they were misled (but did specifically say they weren't delusional), which led to quite a lot of fan hate in her direction. The war fairly ended with the release of the seventh book, because there really wasn't any reason to fight after that.
Notable in this ship war were the "Harmonians," the Harry/Hermione ship's lunatic fringe, who were probably responsible for most of the wank with their conspiracy theories, insistence on seeing symbolism that didn't exist, and invocation of Death of the Author when it was pointed out to them that said symbolism didn't exist. They're mostly gone now, though.
HMS Harmony has been re-fueled and re-armed by the author herself!
In any case it didn't really help that the films tended to play up the scenes between Harry and Hermione while fumbling the scenes between Ron and Hermione by playing up Ron's idiot tendencies.
With the release of Breaking Dawn and Bella choosing Edward and marrying him, and Jacob imprinting on Bella and Edward's half-human, half-vampire hybrid daughter, Renesmee, despite author Stephenie Meyer's writing suggesting a possible romance developing between Jacob and Leah, shipping wars continue, albeit over Jacob/Leah (or "Blackwater") and Jacob/Renesmee. Meyer herself has rebuffed any indication in her writing of Jacob/Leah suggestions, saying Leah has "absolutely no romantic interest in Jacob". Despite this, Meyer's stated interest in writing a possible sequel series to the Twilight Saga, featuring Renesmee's or Leah's POV, and likely featuring Jacob heavily, has served to ignite further flame wars between Blackwater and Jacob/Renesmee shippers.
The Hunger Games: Team Peeta vs. Team Gale. Even with the release of Mockingjay, and Katniss ultimately choosing Peeta, marrying him, and having kids with him, the epic war over whether Peeta or Gale is better for, or "deserves", Katniss more has reached staggering proportions.
Perhaps the oddest fandom to have this going on is Les MisÚrables of all things, vis, Marius/Eponine vs. Marius/Cosette. The stupidest arguments from each side are that Marius/Cosette reeks of boringness and that Marius/Eponine shippers are so socially locked out that they feel better looking up to a street urchin. Try not to trip on the Eppie Sues and avoid any variations on the phrases "First Girl Wins" or "Stalker with a Crush" if you want to keep all your limbs.
Timothy Zahn may have initially written Mara Jade as a Love Interest for Luke Skywalker; at any rate, his ending of The Thrawn Trilogy certain set the foundation for a relationship. Other writers had other ideas (including one who wanted Luke to be with Callista Ming instead), and Mara ended up not-quite paired with Lando Calrissian. On Zahn's return, he retconned Mara's implied courtship of Lando to a spying mission, and to further hammer the point home had Luke propose to her, which she naturally accepted. And then she was killed off some time later, which many angry Luke/Mara fans viewed as Ship Sinking by vengeful writers (though it probably wasn't, or at least had more to it than that).
In the New Jedi Order cycle, which of Jaina Solo's suitors she prefers (if any) is strongly dependent on who's writing this month's novel. Even after that, Troy Denning broke up her and the "winner" in his trilogy of very silly novels taking place immediately afterwards, reportedly because he doesn't like the couple. Hilariously, though, Dark Horse Comics seems to have gotten in the last word by setting up an Empire run by a dynasty with the New Jedi Order winner's last name... and Force-sensitivity.
What evidence remains suggests it was a ship war for the ages, with poor Professor Baeher and Amy taking the worst of it. Now if someone only found some nineteenth-century fan fic in a trunk somewhere...
Actually, the STSC still lives. The Jo/Laurie "essay" in the Ship Manifesto LJ comm is full of Amy bashing, Relationship Sue calls and "Jo/Laurie OTP!" bitching from both the rant's author and the commenters. It has even reached this very wiki, sadly.
A common debate is whether or not Firestar should be with Spottedleaf or Sandstorm. And let's not even get started on Cinderpelt, who had unrequited feelings for him that he was oblivious to.
Funnily enough, Crowfeather has three canon love interests (Feathertail, Leafpool, Nightcloud), but there's little to no Crowfeather/Nightcloud faction to argue against the Crowfeather/Feathertail and Crowfeather/Leafpool shippers. This seems to have extended to even the authors themselves, with constantly contradicting statements between two of them about whether Feathertail or Leafpool was his true love.
There are the Lionblaze/Heathertail, Lionblaze/Icecloud, and Lionblaze/Cinderheart factions, the former two often despising Cinderheart. As for Cinderheart herself, there's the question of her aforementioned pairing with Lionblaze or Jayfeather/Cinderheart.
Who should Jayfeather be with? Cinderheart? Willowshine? Half Moon? Kestrelflight? Poppyfrost? Briarlight? His stick? A question that no one seems to know the answer to until Sign of the Moon.
Then there's Ivypool/Bumblestripe vs Dovewing/Bumblestripe, Dovewing/Bumblestripe vs Dovewing/Tigerheart...
Sherlock Holmes and John Watson: lovers or just "blood brothers"? A classic question. Ask it to any serious fan of the books and they will enthusiastically respond — shippers going off on endless subtext rants and non-shippers calling the shippers ignorant and/or delusional. The huge amount of Ho Yay in the 2009 movie just added fuel to the fire.
The Chronicles of Narnia — Don't mention Susan/Caspian to people who ship Caspian/Ramandu's Daughter (aka Lilliandil) or Susan/anybody but Caspian. Just don't.
Peter/Susan and Edmund/Lucy fans weren't pleased when Caspian appeared in the picture, cause it spurred other ships like Caspian/each one of the Pevensie siblings. Most prominently:
Caspian/Susan vs Peter/Susan, which spurred fiction like Caspian/Susan/Peter, since the second film, Prince Caspian. The film supports that accidentally and indirectly, since Peter and Caspian have a feud since the beginning, Peter initially hating and bashing Caspian, while Susan is instantly swept off her feet by Caspian.
Caspian/Lucy vs Edmund/Lucy, which spurred fiction like Caspian/Lucy/Edmund, since the third film, The Voyage of the Dawn Treader. The same as above, this time Lucy wanting to be noticed by Caspian and trying to be like her older sister, while Edmund is revealed at one point to be jealous of Caspian. When Edmund is tempted by evil again, he actually tries to get rid of Caspian, because Caspian opposes Edmund's intention of becoming powerful and rich with Lucy through the magic pond that turns everything into gold.
Caspian/Susan vs Caspian/Lucy, most prominently, but also vs Caspian/Peter vs Caspian/Edmund.
Jane Austen's niece Louisa Knight claimed that, when she was 8-years-old, she observed her aunts Jane and Cassandra having a mock debate over whether Fanny Price of Mansfield Park should have ended up with her Stalker with a Crush Henry Crawford or Edmund, leaving Janeites forever tortured without knowing the details. If only they had conducted their mock Team Crawford vs. Team Edmund ship war in letters!
Team Rebecca got so vocal in the 19th century Ivanhoe fandom that Sir Walter Scott had to write them a letter explaining why Wilfred didn't end up with Rebecca.
Within the Wicked fandom you either believe the story is a Starcrossed Lovers story between Elphaba and Glinda, or you don't. The ship even has several musical casts (including the original cast) and apparently even the author on its side. There are however fans of the ever-popular rival ship "Fiyeraba", Fiyero and Elphaba, which is equally as canon (and more-so apparent in the books and musical).
A Song of Ice and Fire sees Ship To Ship Combat not between individual ships, but between philosophies of how shipping should work. On one hand you have the traditional shippers, who focus on chemistry and how hot a given pairing would be. On the other hand you have political shippers, who pair people up based on political advantage. The political shippers generally concern themselves only with prominent noble characters.
An example is the potential pairings for Sansa Stark. The romantics love to match her up with Sandor "The Hound" Clegane, the only living character, as many shippers claim, with whom she had mutual chemistry. The politicals point out that the Hound has no political influence, having deserted his own liege lord, and therefore a match with Sansa would be of no value. Also the living part may or may not still be the case. They prefer to match her up with people who could offer her power, typically Harry the Heir or Aegon Targaryen. She has yet to meet either of them face-to-face.
You're forgetting Petyr/Sansa, which as of the end of A Feast For Crows looks like it could possibly happen (especially given as Sansa's final chapter in the book is one long hormonal prelude that reads like her sexual awakening, and concludes with the two of them kissing). Petyr/Sansa shippers fall into the "political" category and are some of the biggest "Sansa for Queen in the North" supporters you'll find, as he clearly intends to raise her up via marriage to Harry, and while there are a few people who ship both Petyr/Sansa and Sandor/Sansa, by and large these two factions detest the other ship.
Robb has this going for him as well. In one camp, we have the One True Love story with Jeyne Westerling, which often finds a way to somehow avert The Red Wedding, while in the other corner we have him either going trough with his marriage to a Frey-girl or having him wed a more powerful player, like Margaery Tyrell, in order to win the War of the Five Kings.
Artemis Fowl doesn't have any portmanteau couple names, but the battle between Artemis/Holly shippers and Trouble/Holly shippers doesn't look like it's going to stop anytime soon, particularly since neither side can be Armed with Canon yet.
A slightly lesser debate is Artemis/Holly versus Artemis/Minerva. Some people can be very very cruel to poor Minerva...
A in-universe example is The Iliad: Helen's suitors (plus Agamemnon and Odysseus, who, being already married, were out of the competition and chosen as referees) had swore they'd do anything, including war, to defend Helen's marriage to whoever was the lucky guy, so when Paris kidnapped her from Menelaus (the lucky guy who won Helen's hand) they raised their armies, involved anyone else they could and marched on Troy, while the Trojans (and, later, their allies) did the exact same thing to defend the Paris-Helen ship.