Wordpress Permalinks Not Staying

The problem is indeed most-likely the sCategory Permalink plug-in (the one that gives you /%scategory%/. 404s are somewhat common. Go to Options | Permalinks page in Site Admin and click Save Changes to regenerate permalinks. They way to confirm this is to use WP-default permalinks to test behavior. If all is working well, it is the sCategory Permalink.

If this isn't working, publish your .htaccess and that will help us troubleshoot better.

I'd be suspicious of something that is periodically overwriting your .htaccess file. When you set the permalink options, it updates .htaccess. If those settings are being "lost", there might be another piece of software running on your site that is mucking with the .htaccess file and removing or overriding the WordPress settings.

It seems that something else is automatically changing your htaccess file and overwriting the permalink settings.

What bvandrunen suggested may work. If not, you could set the permalink settings to what you want and then immediately change the permissions of the htaccess file to prevent anything from modifying it. I would suggest using chmod 644.

Naturally, a better solution still would be to find the script which is modding your htaccess file and get rid of it... but this fix should at least keep your permalinks working!