I think I might be down to my last possible suggestions now.

Do you by any chance have a multi-monittor setup? If so, try disabling other monitors so that you are only using your primary monitor whilst playing Painkiller.

Are you running an SLI configuration? If so, disable SLI whilst playing Painkiller.

Anyway, the vsync-off stutter is probably to be expected. If your PC is fast enough to have seriously high framerate in the game (modern PC and older game will often result in this scenario) then you'll get framerate related issues like graphical tearing and possibly stuttering (simply because your graphics card is many frames ahead and your display has to catch up). So, often you need to turn vsync on to throttle back your GPU. Though as you say, this isn't the main issue itself. But moreso, Painkiller is an old enough game that it actually uses physics calculations based on framerate, so if you are running a fast machine with high framerate, you can jump higher and there is a rope bridge at one point which a high framerate will cause to bounce up and down way too much making it throw you off the bridge and thus be uncrossable, so really, you ought to use vsync or setmaxfps anyway.

My guess is that the vsync is going to be the 'solution' here. The lack of it lets it process the game faster for some reason so it loads levels faster but causes your slowdown. With it on your gameplay is perfect but loading times are too long. Now long load times are a known issue for this game and it may be that you have to put up with it (not ideal I know).

One last option, and I've no idea if this is even a viable solution as I don't know whether these settings only take place after a game is rebooted, is that you could try using your nvidia tools software to control the vsync for the game. Run the game in a window (even a full size window) so that you can Alt-Tab to other windows. When loading a game Alt-Tab to the nvidia tools and turn off vsync so that your game loads faster. Then once loaded, Alt-Tab back to the nvidia tools control panel and turn vsync back on so that you don't get slowdown in game and that the physics are back to how they should be.

Anyway, you mentioned an AMD optimizer. It just so happens that DNF installs an AMD optimizer (though I'm on an Intel Core 2 it still installs it) and for me the loading times for DNF are between 10-25 seconds (different levels vary in loading times). It uses a modified Unreal Engine 2.5. I wonder how your machine would get on with it?