No one else? Did anyone else import email into iCloud from Gmail/Others?
One other piece of info - I attempted once more to relocate all the contents of my Inbox folder into the Archive folder just to try my luck. Same lack of search results in the Archive folder. I then moved everything back to the Inbox. At that point, I noticed that no messages were "searchable" after that date. Essentially, me moving the messages caused them to break some kind of searchability link and become un-retrievable via search. As new messages come in since then, they show up fine in search results, but I now have a black hole before 1/15/12 (the day I executed the above).
My iPhone email client has stand-alone search capability, so I get proper search results when I search there (including messages that would not return search results on icloud.com) - but only for the ~200 recent messages it caches. If I click "Find more on server" it immediately comes back with 0 results on server.
This seems like such an unlikely / simple problem for this day and age... why on earth is iCloud.com search ability broken?