Found this one by accident and according to Microsoft it is working by design, although no one has explained why it was designed that way. In any case the issue involves folder level security and anonymous access. Seems that if you break inheritance at a folder level you will not be able to allow anonymous access from that point down.
We have tried many different ways to get around this finally deciding on a event trap to provide a way to get this to work the way we want it.
One nice new feature in MOSS is the ability to set folder level security...well I guess "nice" is a relative term. In any case if you need to figure out what the security on a folder is you can use the following code (this assumes that "thisFolder" is a SPFolder that has already been set)
SPListItem thisItem = thisFolder.Item; //Convert the SPFolder into an Item. I think this only works in a document library.
SPBasePermissions thisItemsPermissions = thisItem.EffectiveBasePermissions;
//Check to see if a user can upload a document
if (thisItemsPermissions & SPBasePermissions.AddListItems) != SPBasePermissions.EmptyMask