WebDoctor you are absolutely right in what you said. However in most cases I have checked the servers for their configuration or to see if a hash might be present in URL's. In all cases (except for 2 where there were hashes in the URL) I have found it to be a matter of Googlebot simply not being able to "read" some URL's properly. The disappointing fact is that it seems to be selective with no real pattern to it. While some pages are indexed fine others are left out.
I have even tested the usage of sitemaps and although it does indeed help to some extent it still is not enough.
I think the solution for CMS systems is to actually take into account mod-rewrite when programming the CMS itself. The disappointing factor is that nearly all CMS solutions do not. As many have grown well past beta stages they do not want to go back and take the time to address the issue.