Is there strong evidence that Classical Chinese was ever spoken?
I think doubts about Classical Chinese having ever been a medium of oral communication are quite appropriate. There are several things to consider: 

One, the fact that the characters are relatively few is not so troublesome as they designate morphemes rather than words. Language has but a few sounds, a number of ways to combine those sounds phonotactically into clusters and rhimes, a fair number of morphemes made up from combinations of these, a wide field of words made up from morphemes, and an endless variety of sentences that consist of words and the syntactic constructs they enter into. 

Also, there is a limit to how many distinct signs an individual can handle, so if you go and invent a script of whatever type, chances are that when someone puts you to the test, you will only be able to reproduce so many of them—hundreds maybe, thousands even, but likely not tens or hundreds of thousands distinct graphical signs. Therefore, observing that Classical Chinese uses less than ten thousand signs tells use more about the human mind in general than the Chinese language in particular. 

Given that language (speech) is an innate capability of humans, but writing is a later, culturally acquired skill, we should also think it likely that people are ordinarily much better at the former than they are at the latter, meaning that if the plan of your script means to invent one distinct graphical sign for each morpheme (which is the case in Classical Chinese to a certain extent, as there may be up to roughly a thousand distinct pictorial signs), you'll likely end up with a repertoire that has less signs than your speech has morphemes.

Two, all scripts are defective when compared to the speech that they record. Whether you look at Egyptian hieroglyphs, Mayan writing, the Phoenician consonantal alphabet, or Arabic, you will always note that they leave out aspects of speech (e.g. vowels) that writers of the Latin alphabet take for granted. Writing in Latin letters also leaves out quite a few things like intonation, mood, facial expression and so on. 

To me, it looks like the classical inscriptions of China, while born by speech, as it were, are condensed, concentrated notations that are reduced to the essential parts, a bit like a map will omit many details of the territory, or beacons in the sea only mark the essential points for navigation. 

Third, it may be a misconception that two or three thousand years ago, anyone who expressed themselves using the medium now subsumed under the title of Classical Chinese spoke the same language. It is a misconception similar to thinking that today, someone who writes literary German, English or Arabic will also speak like that, and that all writers of one or the other of these literary forms of expressions will be able to converse without hindrance. To the contrary, many writers of German, Arabic, Greek or modern Chinese use that medium essentially like a more-or-less foreign language. We should not assume it was all that different in ancient China.

BTW there are (as of Unicode V8) around 80'000 distinct Chinese characters encoded in Unicode, with many thousands more known that remain unencoded. No-one in history ever knew or used all of these at any point in time, and no single dictionary collects all of them; rather, it is what many hundreds of millions of people have managed to come up over the course of thousands of years. When you look at the number of characters used to write particular pieces of literature, you will invariably find that classical and modern literature alike can make do with but a few thousand characters.