The evolutionary explanation is that cuckoos are making it less likely that magpies with the ability to tell cuckoo eggs from their own eggs will pass their genes on to the next generation.
That doesn't rule out the "Mafia hypothesis," but it doesn't seem very likely. How would a magpie know ahead of time that cuckoos are vindictive? Plus it would be making quite a claim about avian intelligence to conclude that magpies who had had a bad experience with cuckoos in prior nesting seasons would make the connection between evicting an alien egg and having the nest attacked by a cuckoo days later, especially given the wide variety of possible predators and that attacks most often occur when the nest is unattended.
--Percy