Chemiotics II (luysii) had a very interesting post on his blog about the number of proteins of a given length that can be constructed from the entire mass of the earth. Comparing the masses of amino acids to the mass of the earth, he demonstrated that all the earth's mass will be pretty much exhausted with all combinations of a protein that's only 41 amino acids long, which is peanuts as far as your typical protein goes. Such calculations have great relevance for the origin of life if we are to understand the design and evolution of biomolecules.
One can ask similar questions about crystals or small organic molecules. For the latter one can similarly show that the number is much more than the number of atoms in the universe. But most naturally occurring organic molecules have a preponderance of certain fragments like benzene rings. Similarly, there are only a certain rather small number of symmetry groups for crystals. Therefore it seems that in reality, we are dealing with modular units which are much smaller in number (although still quite large) rather than the bare individual units which compose proteins/small molecules/crystals. Thus once these modular units evolved, natural selection probably worked on them instead of trying out possible combinations of their individual atoms. Also remember that natural selection can work on a population of individuals- any kind of individuals- if one of them shows even the slightest advantage with respect to replication. In case of sequences of amino acids, such replicative advantages could arise from several features; stability, charge distributions that could serve to protect the sequences from aqueous hydrolysis or attract one sequence to another, or conformational flexibility that could serve to effect flexibility in the functions of the sequence. Any one of these features could serve to "fix" a particular sequence or group of sequences in a pool of sequences.
In case of proteins for instance, one should ponder how many of the many possible sequences considered could be energetically favored. Some sequences that pit bulky or similarly charged amino acids next to each other could be disfavored by steric and electrostatic factors. Also in case of proteins, the conservation of 3D structure relative to sequence must have been a boon for natural selection. For instance, there's an enormous number of sequences that can fold up into alpha helices (although certain amino acids are favored and others are disfavored) or sheets (where amino acid preferences are not as pronounced). Thus one gets the feeling that natural selection could have some flexibility in designing sequences that would fold into energetically favored secondary structural motifs. However this would not work as well for the active sites of enzymes, where very specific amino acids need to be located in very specific positions in order to effect catalysis. But even here, certain amino acids such as histidine and lysine are interchangeable in terms of their acid-base catalysis roles.
A particularly interesting case that comes to my mind is that of amyloid. Once thought to be the province of only proteins like ß-amyloid, it has now been extensively shown (most notably by Christopher Dobson of Cambridge University, for instance see Nature Chemical Biology 5, 15 - 22 2009, doi:10.1038/nchembio.131 ) that virtually any protein can form amyloid under the right conditions. Amyloid may have been evolution's dream, since it could have tremendous flexibility in picking sequences and coercing them to form amyloid-like structures under the right conditions. As work in which I participated demonstrated (Biochemistry, 2008, 47 (38), pp 10018–10026, DOI: 10.1021/bi801081c), the simplest of changes in conditions like temperature and pH are enough to drastically modulate the architecture of amyloid assemblies.
Thus, while there was potentially an infinite pool of possibilities to design proteins from, as evolution proceeded, I think that the funnel of possibilities became narrower and narrower as the units needed to achieve optimum design became more tailored and building-block like. It's a very interesting question to contemplate the details of this matter.
5 hours ago in Variety of Life