I have a lot of experience with large numbers of combinations. For a recently developed web shop, we had custom products. Each product had at minimum 5000 combinations, and we encountered 500 server-side errors like you have. It was cumbersome to load the pages and administer.
So, we ended up reducing the number of combinations per product, and having more products instead. So for instance, we had one shirt available in red, white, blue and in 8 sizes and with 20 logos available. We moved so that we had three shirts - one in red, one in white, one in blue - with the same options and that helped with performance and errors.
If you are importing, go get the import fast module (just search the forum for it). Kjeld (the developer) made a great module for importing huge amounts of data - it was very nice, and let you set the default combination as well. He's fabulous.