Ok, there seems to be 2 unrelated issues here.
If you are taking a performance hit through sh404sef, try turning on the cache for the site in your global perameters. Once folks have went through you site, your performance problems should go way, way down.
The second issue that you are getting 404s and therefore Google has delisted those pages is probably caused because you haven't purged your sh404sef setup. Every time there are changes to categories, sections and page titles, sh404sef should be purged so that it can replace old information with new information. Find a link that is currently showing a 404, run a purge and then navigate back to that page. It should appear.
If it does not, do a check at the sh404sef forum. sh404sef is now a supported product so if you haven't upgraded, it's worth the money for the improved product and support. sh404sef is the best product out there for custom URLs but it does take some setup and tweaking to get just right.