What a nice post, and nice conversation you two are having here!
It's useful to think about the inmune system. The body needs the right lymphocyte to be around when an antigen is attacking. Just like with computer viruses, there is an unlimited number of possible ones, so how do our bodies handle the issue? There seems to be an interplay between random and non-random lymphocyte production. So if there is no detected threat production will be mostly random, but when there is a threat many copies of the appropiate lymphocyte are made. Also, it isn't well understood how, but despite this randomness healthy bodies don't suffer from "false positives" (imagine a spread of malicious white cells!). Would you grant the inmune system the status of "intelligent" given that it manages to fight against the best virus creator (evolution)?
Genetic algorithms are one way in which these insights are being used in programs but they do create a "box" within which the program's creativity is confined. Nevertheless, how would we know if our creativity has or doesn't an analogous box?