Cluster your n response classes into m clusters, where
m < 1,000. With an incoming instance i assign it to one of the m clusters using your favorite classification algorithm. Once the instance has been assigned to a specific cluster, you just need to run it through a classifier trained on the classes that comprise that particular cluster.
I've used this particular architecture to assign texts to one of n possible "emotions", which I illustrate below. The incoming text was first scored with a binary classifier trained on positive & negative texts. Given the text's probability of being positive (as predicted by the classifier), the text was then routed to either a series of all positive or a series of all negative emotion classifiers where it was a assigned a specific emotion.
This same sort of design should work your case. First you assign your instance a cluster. Given that assignment, send your instance to the next stage - where the final classification occurs.