The idea of analyzing existing recordings for information is compelling. I saw a show about Zipf's law, I can't remember the name of it but the basic idea is to plot data with the symbols on one axis and the frequency of each symbol on the other. Highly structure data that conveys information tends to have a -1 slope on a logarithmic scale. More info:

http://en.wikipedia.org/wiki/Zipf's_law

http://www.peterrussell.com/Dolphin/DolphinLang.php

One of the problems with this approach is that data compression takes advantage of these frequencies so that at maximum compression the slope tends back towards 0 (perfect compression is almost indistinguishable from noise).

To me, this is the most likely reason why we haven't discovered extraterrestrials. Without the decompression/de-encryption key, we have no way of seeing the sea of data that's probably being transmitted all around us. That and the fact that aliens have probably learned how to communicate with neutrinos because they are able to build arrays of nano-detectors that can sense the perturbations that are too faint for us to see. Also the beams are probably directional, not broadcasted for all to see. So looking for direct evidence of a civilization, something like a heat signature or particular arrangement of matter, is probably going to be more fruitful than eavesdropping on communications.