Average message complexity for the election problem on graphs
I don't know of any results in distributed computing that state bounds on 
average message complexity that are independent of the network topology.

Let's assume you have an algorithm $A$ with average message complexity 
$\Theta(f(n))$, for some function $f(n)$. While such a universal bound 
sounds quite powerful, the problem (as I see it) is that this tells you 
very little about $A$. If someone implemented $A$ for a specific class of 
networks, the $\Theta(f(n))$ bound becomes meaningless, as it is the 
average over all network topologies and unique id assignments, whereas 
worst/best-case bounds would still apply.