I had this happen to me at work. I was working with Magento and looking at the image uploader for products and realizing that folders were being created as "nobody". My problem was that the actual Apache server was on one box while the files being served were on my local machine. So Apache was creating folders under a user that wasn't on my machine (www-data).
Something to think about is using [man]umask/man and setting it to 0 to see if that will create the folders in 777 mode. Not sure precisely where you could track it down. I would pull the code you have running out for a second into a test script and strip it down to just a very basic mkdir() call. Then inspect the results. I'd then add code back in to see what could be causing it.
I never did find the issue, so I just had to deal with it; however, if worse comes to worse, you could create your own mkdir function which calls mkdir, then chmod, then chown.
On the other hand....
Running PHP in cgi mode isn't going to kill your server; however, it may run slower than normal. How much slower depends upon precisely how much load the server is getting.
Sorry I can't be of more help.