全然 began to be taught as only being followed by negatives between 1950 and 1960.
As mentioned in in the comments above, とても can actually be, and very often is, used with negatives. And in colloquial Japanese, 全然+non-neg. is currently, and likely always has been, frequently used.
In normal Japanese, you are correct in your presumption that double negatives resolve to positive. ない、なくない、なくなくない、 and so on, will continue to alternate negativity as you add more negatives to the end. However, 全然 itself does not contain any kind of negative aspect; that still must be attached to the target of inflection (an adjective or verb).
If I were to hazard a guess as to why 全然 became restricted to negatives, I would say that it is likely related to the Japanese language's strongly head-final nature. It tends to favor very long subjects and short predicates, which means that in many cases, you can't understand an utterance until the verb comes at the very end.
As a result, Japanese has developed a number of words like 全然 which preview some aspect of that verb; specifically: negativity. Following is a list of some such words:
These are essentially always followed by a negative, and so act as nice indicators of what will come, perhaps much later in the sentence. It seems to me that the inverse (things only used with the positive) exists as well, but I can't think of any examples.
There are several detailed responses over on Yahoo's Chiebukuro that you may find interesting, as well.
