Any suggestions for Taxonomy scaling and performance with 1073 terms?
1000 terms is not so bad, really. I am inclined to believe the number of terms in your vocabulary is not what has the most impact on response time, as MySQL can handle much larger datasets out of the box.  One factor to consider is the hierarchy of your taxonomy, or the number of levels it has. A vocabulary with 3-level-deep hierarchy will be much slower than a vocabulary that is implemented as flat hierarchy. 

Good-luck