Welcome to the Q&A Forum

Interesting situation...and very frustrating for you, I'm sure. You mentioned this below: "I checked 'cached snapshot of page' in Google Toolbar for the pages that weren't being indexed, and it showed up as a 404 error. " This sounds like you had some sort of technical error.  But some things still don't add up for me.  It kind of sounds like your pages were not resolving for Google.  But, the odd thing is that if Google sees a 404 error, they keep trying for days, weeks or even months before they conclude that the pages should be removed from the index. I don't have an answer for you but the first place I'd look is to make sure that your robots.txt file is not blocking Googlebot in some way.  I'd also check server logs and perhaps check with your host to see if there was some significant down time for the site. If there was a technical glitch, and the problem is now fixed, then your pages should come back into the index without you doing anything. I'm pretty certain this isn't a penalty issue though.