Hey Michael, if you've flicked all the switches and still no improvement, I'd do a couple things.
1. Are the categories dynamic or static? Dynamic will add overhead. Specifically in your case considering product count.
2. Have you made any customizations to the category page vb files? Any random calls not out of the box?
3. Take a peek at the server setup. All i's are dotted, t's crossed, etc.. shared hosting? dedicated? SQL on a seperate box?
I'll make my shameless plug that
www.resposio.com handle some sites that are much larger than 31k products, all smokin' fast... If you're good with your host and/or network, disregard :)
I mentioned 24 products to a category with the disclaimer - (that's not aimed only at a BV Application). So I'll clarify my .02 cent usability suggestion that categories in general should stay at a reasonable number. I say 24 because a typical trend is a 4 x 6 grid (variations are abundant, really shoud be decided by place & time).
Sort of unrelated, I'm not up to speed on your products, but can they be classified by Volume #? Editions? Characters? Theme? etc.