Lion vs. Hyena (Interspecific War)
Lions and hyenas have been waging war against each other for as long as humans have observed the interaction between them.
During the spring of 1999, a set of battles raged between a cackle of hyenas and a pride of lions in the Girawa woreda of Ethiopia. A report from the United Nations Office for Coordination of Humanitarian Affairs - Ethiopia (UN OCHA-Ethiopia) reported that when the described round of battles were finished 35 hyenas and 6 lions had been killed. One local reported that the war between these two groups had started 45 year before "when a lion escaped from Emperor Haile Selassie's palace menagerie in Harar and wreaked havoc on a hyena family."
In their book Hunting with the Moon, author/explorer/filmmakers Dereck and Beverly Jouberts document ongoing battles between lions and hyenas in Botswana. A quote from that book indicates that "anyone who watches a violent contact between lions and hyenas, one that is not related to food, can see plainly that there is a blood feud between them that is uncannily similar to those at which our own species is so adept."
Wolf vs. Wolf (Intraspecific War)
In Yellowstone National Park (USA), there are several distinct packs of wolves that have known territories and sometimes wage war against each other. They also participate in hunting parties that sometimes lead them to 'steal' a moose or bison from a competing pack's territory.
The PBS documentary series Nature followed the fate of one Yellowstone wolf pack in the episode In the Valley of the Wolves. The episode transcript reports that "in 2004, the Druids [name of wolf pack] once again suffered terrible losses; longtime alpha female #42 was killed by members of a rival pack, and the aging patriarch was found dead in the summer. At the same time, however, the neighboring Slough Creek pack began to spend more time on the northwestern boundary of Druid territory. Their incursions into Druid turf culminated in a decisive battle in 2005 that ousted the formerly dominant Druid wolves from the Lamar Valley. Two adult female Druids died that year — one killed by the Sloughs — and no pups survived. The pack was reduced to just four members, and looked to be nearing its end."
The Wikipedia entry for wolves indicates that 14 - 65% of wolf deaths can be attributed to predation by other wolves, and that up to 91% of wolf deaths occur within 3.5 km of the respective pack's territorial boundaries. (Supporting references for cited figures are provided as reference numbers , , and  on the linked web page.)
Edited September 6, 2011, to add more information and links to supporting documentation.