I would suggest topic based resource pages not a mathematical division of the site but a meaningful categorization that will be useful to visitors. That will attract deep links and pull the spiders deeper into your site.
are you getting any links to the deep product pages?
without those deep links you will probably see yourself hovering around the ~10% of sites in index since that is what google seems to be crawling and finding regularly on your site. Especially if your internal linking was suboptimal pre July '09.
Make sure that google can crawl, and re-crawl, all the pages you want to be found in the index. Link to, and interlink, your product pages well.
Build links to the product pages.
This should help increase the number of your pages found in the index.
I have about 12,000 pages. I have internal links on every page I created content for(about 1,500 pages. So I think I have internal linking well under way.
Is there an easy way to build deep links from other sites? If I have to create 3-10 liks from other sites to each of the 12,000 pages I have it will take years. There has to be a solution. Do I need links to each page or just to matbe 10-15% of my internal pages?
Is there an easy way to build deep links from other sites?
You need content that people want to deep link to. You were part way there with your resource pages. As I said before identify a classification of your content and create a resource page for each classification. Then look for specialist links for those classifications. Details would depend on the nature of the site and content but for "costume" I would expect there to be specialist niche sites around that would happily deep link to a relevant page.
Link building is more than a mathematical exercise to game the search engines. Real links from interested sites will bring traffic in their own right. A quick and unscientific eyeballing of recent hits on one of my sites showed about a third of the traffic being from links rather than bookmarking or search engines.
Are they pages with products on them or useful content or are they just pages to simply rank in the search results? Sometimes Google won't index massive amounts of pages if they feel the pages are there just to infiltrate search results.
Matt Cutts recently talked about this at SMX, I will try and find the link to the video for you, but he essentially said that google prioritizes the amount and depth of crawl based upon pagerank.
gn_wendy is correct, get some deep links to those pages and check out the recent videos of him talking about the "pyramid" idea.
Also check out the articles about this on seomoz.
tadden, assuming you don't have duplicate content issues or title/description issues your pages don't have enough PR flowing to them to rank them all.
The fix is to ensure PR, both internal and incoming, is able to easily reach the pages you want indexed. How many clicks away is the hardest to reach page on your site?
Also, there aren't 12,000 costume related keywords that will drive significant traffic, you may want to focus on making the important pages more prominent. Good luck!
Diving into the longtail I am sure there are more than 12000 terms that can drive traffic to a costume site.
Sure, shorthead terms like "costume" or "buy costume" won't ... but add variables for the longtail searches like colors, themes, genres like [XXL rubber latex widget suit] and it all makes a little more sense.