I have a feeling that the Avatar scenario is no more likely than tall blue-skinned humanoids. Our notion of intelligence pretty much defines it as collection of thought processes that end up manifesting themselves in the development of technology. Dolphins may be extremely intelligent on some scale unknown to us, but we don't observe them building submarines or decoding radio signals, so we don't consider them to be human-level intelligent. Similarly, to them, we may appear as these strange shore-bound small amphibious quadrupeds who carry various strange amulets on their bodies with which they do various strange things, all of them being of completely no use or interest to an average cetacean. I'm probably exaggerating cetacean intelligence a fair bit, but I just wanted to illustrate how closely our definition of intelligence is bound to the availability/use of technology.
Suppose bottlenose dolphins have an uncanny ability to "read minds" and interpret thoughts and emotions of other bottlenose dolphins (but only of individuals of their own species -- not of porpoises, humans, etc.) to the same or even better extent than we humans can read minds of other humans, but due to the accidental specifics of their bodily layout and environment (no limbs with which to grasp and manipulate objects, unsuitable environment for the use of fire) are unable to develop any semblance of technology. What would those "super-dolphins" look like to us? I have a feeling they would still look a lot like dolphins, and we, without some very specific/expensive/targeted research, probably would have never even realize that we are living right next to some "super-intelligent" animals.
Life is quite messy and obvious. It seems quite likely that traces would exist.
Also, take into account the possibility that other intelligent life might be more biological than technological (e.g. interconnected intelligence without technology like in Avatar).
Then factor in that intelligent life might be microscopic or just tiny.
It's really not hard to imagine that the search for alien life is a problem of asking a question for a rare/over-specified solution.