Well, first I would suggest never to change core files. There should really be no need to in the first place.
Second, if your host won't work with you to figure out your problem, then to be quite honest, they must not be a very good host. They really should be able to help you with setting up software to work with their server's settings.
As to why your last case would be happening, I can't really say, but I do see in the troubleshooting article this tidbit:
Quote:Some servers are configured so that scripts cannot be executed from folders with weak permissions. We suggest you start with the strictest permissions and relax them if that causes permissions errors. Unfortunately, there are many permutations of how servers can be configured and not all are reasonable or rational. You may have to experiment to see what works for your situation.
It may be that your server is preventing anything with a .php extension from executing depending on the directory's permissions. Whether that affects non-existent files, I'm unsure; regardless, as stated above, you will have to find a suitable set of permissions for your server. Your host really should be able to provide you with that information.