Permissions are hosed somewhere, most likely in /usr/local/frontpage- compare to other machines. (other NON-suexec boxes)
R U sure /scripts/initfpsuexec wasn't run?
or /scripts/fpsuexec ?
Do *any* webs work?
Or just new ones created recently fail... and when? When people log in to Frontpage? What does the end user see?