Search Indexing not working correctly though cron is running successfully

Issue Summary

Well into development on a site I discovered that the site was not indexing all of the nodes on the site during cron. I then tried the usual trouble shooting routine... checked for nodes with php or odd characters, deleted the cron_semaphore and cron_last variables, ran cron with debugging code to check for specific problems and I even deleted all nodes on the site and created new nodes to test. In fact I tried every solution listed on this page: http://drupal.org/node/553430 and then some, but nothing worked. Then in desperation I tried installing the system in a brand new folder from scratch. Low and behold normal nodes with only a few lines of innocuous text that I typed in myself don't get indexed at all. Regardless of how many times I run cron, the search settings page shows that the nodes on that site won't index.

I know the first thing people are going to suggest is that it is a server issue, but I am running this site on two completely different servers (one mac, one linux) and all the other sites on those servers run cron with no problem (and those sites have many more nodes and modules installed). It's also not a server load issue since one of the servers is used only for testing and is not accessible to the web.

Any assistance would be greatly appreciated. I've been up all night trying to get this resolved for my client, and I'm out of ideas.