Give 0777 a try. If it works, complain to your ISP that their configurations are bad. I personally would not want to run at 0777 on a publicly accessable site, but if that is all that works, you have to either run that way, get the ISP to fix its problems, or change ISP.