There are many more, I believe. A couple that come to mind:
-
bee eating birds work with human wild honey seekers by locating a hive and leading the humans to it. Humans get the honey, the bird, the bees.
-
certain mid-sized tuna (the skipjack, maybe?) have learned to hunt small fish with whale sharks. The tuna do the broad focusing of a school and the whale shark focuses that into a dense ball. Then both go at it.
-
crows who follow wolf packs and lead themto weakened herd animals by imitating a howl.
As for protection alliances, I do remember about wrass cleaning stations and what happens if an inexperienced predator decides to attack the cleaners. The other fish in line (including their own species) will drive the attacker away and keep it away. The fact that predator and prey suspend the chase while waiting in line amazes me. How long did it take to work out the real importance of orderly patient, etiquette for all this?
I also seem to remember reading about some economist who studies natural behavior and works out the economic math of such behaviour in terms of costs and benefits. According to him, we still have a lot to learn!