Frontpage extensions (not related to this issue)
This may actually be the cause of the problems. Frontpage has a tendency to takeover a website and modify things that do not directly relate to it.
What platform is your store hosted on, windows, linux, freebsd etc.?
My guess is that it is a Windows platform since when you you look at the Preference >hosting services setting you are using security at shopping cart url but not at the backoffice url.
The file where the settings for your store are saved is in a file called <storeid>.aa where <storeid> is your login name for the backoffice of the store. There should only be one actual copy of this file and another "symlink" of the same name. On windows servers the actual file is in the stores shopping cart (usually sc) cgi directory and the symlink is in the store's backoffice (usually ss) cgi directory. In a Linux, Freebsd, Solaris install the actual file is in the ss directory and the symlink is in the sc directory. Note that windows does not actually have a "symlink" file type so this is simulated by ShopSite by putting special content in the file to indicate where the actual file is located.
In either situation if the symlink is replace with the actual file odd behavior can occur because one file will be modified when you save settings from the hosting services screen but the other will not be changed. An indication that this is happening is that when you save the secure settings they don't change in the backoffice. So you need to check and see if the appropriate directory for your OS has the real file and the other directory has the symlink file. On windows the symlink file (in the ss directory) should be small say 10-30 bytes and the real file will be 300-1000 bytes. On linux or the other unix OSs the file type will be a symlink.
So check your files and see if they are in the right location and the right type. If not you can make the one a symlink on Linux or other unix os but you will probably need help to recreate it on windows.
Note that backups usually don't keep symlinks on unix/linux systems so if the store was restored from a backup this could have cause this issue.