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. - Aaron B. Hockley