MadeWillis - 7:35 pm on Apr 29, 2010 (gmt 0)
How well do you rank for your top keywords? A 10 year old site with that many pages may be able to do really well without any external link building effort. Be careful outsourcing this as well. Just be sure you have a hand at selecting the links you want, where to point them and when and how many to buy (if you will be buying any). This is where a lot of people get themselves into trouble, however the 10 year old domain does come with it's advantages.
You could also develope a good formula for generating your title, description and keyword tags so that you don't have to wait to touch every single page. Then you can pick and choose from the top and work your way down optimizing the most profitable pages first.
Read up on siloing content and best practices. Works very well on large sites with variance in product line.