Having to wait for things to die can be restrictive (but genomes are declarative, what does that buy?). Roughly, with what amounts to the assumption that Lamarckian evolution is more or less not true, you can characterize evolution's learning power as almost as good as PAC (query: statistical query learning evolution).
See alsos:
http://vserver1.cscs.lsa.umich.edu/~crshalizi/weblog/601.htm...
http://arxiv.org/abs/1211.4037: Natural selection. V. How to read the fundamental equations of evolutionary change in terms of information theory
1. You're right, our intelligence is the same thing. Intellect is a statistical creation that makes us good at surviving.
2. But usually, when people talk about our intelligence and our having goals, they aren't talking about the fact that we statistically exhibit tendencies towards self-preservation (which is what we're talking about viruses doing). It's that we literally have conceptual goals, which can be written down ahead of time and talked about.
aka you won't find a virus with a to-do list. Conflating that intelligence with viral 'intelligence' is kinda disingeuous.
--
That said, I do agree that we might/will find alien life that looks nothing like what we expect and has 'intelligence', for some reasonable (non-virus) definition.
I would not be inordinately surprised if we managed to find this in the motion of waves in the ocean, or in the swirling gases of the sun, or the gravitational interactions of the asteroid belt, or in tremors in the earth, or in hive-minds of billions of ants. And I definitely reject dualism and fully expect that a human brain simulated in a computer would be as intelligent as we are.
I'm not sure what the criteria for an 'intelligence medium' is, but it seems to require sufficiently high entropy to allow for complex patterns to form, but not too high - there has to be enough order and especially a not-too-high temperature such that self-contained systems can form and replicate without being blurred back into the whole system.