In searching for an answer to the difference between "seek" and "search" I sought the help of several sources. I looked in the German dictionary, Shakespeare, and the King James Bible.
My feeling after examining these different sources is that the current "difference" between these words is idiomatic and that trying to pin down the exact meaning difference between these words is futile. Or trying to give a usage rule will meet with many exceptions.
Seek comes from middle English (http://www.etymonline.com/index.php?allowed_in_frame=0&search=seek&searchmode=none) and is also used in German (suche.) German (to the best of my knowledge) only has one word for this idea of "looking for / examining, etc.) "Search" and "Seek" both mean "suche" in German and expressions that in English have distinct usages don't generally have that in German. "I'm seeking / searching for an answer." is fine in English but "I seek the ocean for the plane wreckage" is odd. In German, however, "suche" can be comfortably used for both.
Search comes into English from old French via Latin and means to thoroughly examine. http://www.etymonline.com/index.php?term=search There is an example "Search warrant." Why don't we say "seek warrant"? In German the word "durchsuchungsbefehl" is used which means literally "through seek order." Warrant also comes from old French http://www.etymonline.com/index.php?term=warrant. So I think if English hadn't had the French influence, police might now be saying "seek / ing order." As in German. I can't prove this, of course. I do think search warrant is a good place to begin when thinking about the meaning of search.
Why the German connection? Because I think that before "search" came into English through French (and possibly also heavy usage in legal things) "seek" might have been the word used in common speech (and in ways we probably would not feel "comfortable" with.) Perhaps someone with a background in older English usage can shed some light on this
In looking through the King James Bible, I found that search seems to be used more for land or physical things (search Israel or search your heart), and seek for specific things, such as Jesus, answers, or abstracts ("seek and ye shall find.") However, I'm not sure if this line of reasoning is valid because the Bible was translated and the original source documents might have had two words, or just one word. I am not a Bible scholar so I cannot say. The Bible also contains the new testament which was written in Greek. I found examples of search and seek in the new testament. Does Greek have one word (like German) or are there two words as in modern English?
In looking through Shakespeare I found many examples of search and seek but the meaning differences were not always apparent. I'm not sure Shakespeare is a good place to look because we are talking about poetry and iambic pentameter, so although search and seek are both one syllable, each word might have had a "feeling" for Shakspeare that doesn't really help us to understand the difference through his writing. The most humorous example I could find was from All's Well That Ends Well: "That seeks not to find that her search implies." If anyone can find a meaning difference there, I think Kenneth Brannaugh is searching for you. (Maybe he's seeking out your advice?). I looked in Shakespeare because I felt there might be a preponderance of one word over another that could shed some light on the meaning. This wasn't apparent to me, however another user might see something I overlooked.
So to sum up, my feeling is that current uses of "search" and "seek" are largely idiomatic and to say that the correct answer for "animals ______ food" is "seek" is dubious. In fact given that historical usage supports "search" (in the sense of exploring land or thoroughly examining a space) I feel "search" is the better option. I think historically many native speakers grew up with the King James Bible as a source of "proper" language and could see the meanings of the words in context, so would have extended those meanings in speech, and have done so since the KJV was released. In looking at the various answers given, I see some great ideas but I think they are ideas about the idiomatic usage and they can't really help to know the difference or boil things down to a strict definition. It would be like trying to find a definition for "spank" by looking at the expression "brand spanking new." If we give a definition for one word someone can say "Yeah but what about this usage in Hamlet / the Bible / The Constitution / Chaucer etc." If I were forced to give definitions based on what I found, I would say that search is used for physical spaces or ideas which have a sense of physical space, as in "search your mind.", and seek is more abstract. We seek knowledge, wisdom, truth, answers, justice. Of course, we play "Hide and seek." and I'm seeking the other person not an abstract. It wouldn't be English without "exceptions."
The word "seek" is still very much in use. A quick search on Google for "seek" + "USA Today" will show many uses of the word seek. "Seek"+ "Daily Mail" also indicates the word is being used. Just this week, there were three instances of it.