http://en.bp.ntu.edu.tw/wp-content/uploads/2011/12/06-Alexan...
While you're correct that fully connected graphs are an extremely inefficient structure for communication or other resource flows, trees are also problematic and not as common in nature as you suggest. One clear problem with tree like structures is that they have zero redundancy. There is only one path between any two nodes. That implies that severing any edge will separate the tree into two unreachable sections. Sever the wrong single edge and you can render large regions completely disconnected from each other.
That's not a recipe for a resilient system, and we see the same problems in organizational hierarchies. In strictly top-down companies, you often hear "I can't do that right now because X is on vacation." There is no way to route around the absense (or poor performance) of a single member.
And, in fact, vascular systems are not entirely tree-like. Veins and arteries generally are, but where they meet at the capillaries, you see a more unstructured interconnected graph. Likewise, the leaves on a tree are not themselves tree-like. Their vasculature is graph-like and semi-redundant.
I think a better way to look at it is as a continuum. On one end, you have trees which have the minimum number of edges to reach all nodes. This minimizes the total cost of building the edges, but also minimizes redundancy and resilience. On the other end, you have a fully-connected (or even multiply-connected) graph where there are many paths between each pair of nodes. That graph is maximally resilient, but expensive to maintain. The particular needs for minimizing edge cost versus handling edge failure will lead you to pick different points on that continuum.
Also, when it comes to biological systems, the evolutionary need to actually build the thing shouldn't be understated. It is very likely that non-tree-like structures would be better but there isn't an easy evolutionary path to reach them. Phenotype essentially arises from "executing" the genotype, and trees are much simpler to procedurally generate than more complex graphs.