SharePoint 2007 permission issue and the 2000 security principals in an ACL

Question

I have been trying to find more information on the issues surrounding an ACL that has over 2000 security principals in SharePoint 2007.  The closest I have gotten is this excerpt from Frank Migacz (http://sharingthepoint.blogspot.com/2010/09/sharepoint-security-model.html)

"Over 2000/5000 security principals per ACL will cause the failure of indexing of items in the scope and all items below that scope. "Does this mean that the system will perform slowly when searching for them, or will the system fail to find them causing permission issues.

I ask because I have been running into the following issue lately: A user will be granted contribute access to vanilla a document library.  No permissions managed at folder or document levels, straight up inheriting from the document library.  They will try to open a document and it will prompt them for their windows credentials.  I have found that changing the permissions on the site, that the doc library sits on, from limited access to read only will alleviate their problem.

Our set up is one app server tw0 sql servers (clustered) running MOSS 2007 Enterprise.  We have definitely breached the 2000 security principals limit.