Nothing just happens for “no apparent reason”. Some new condition has caused this. Most likely a new plugin or update of an existing plugin.
It is possible for a plugin or theme doing something crazy like flushing rewrite rules on every load could wipeout the existing rules. See this ticket for more info: http://core.trac.wordpress.org/ticket/18450#comment:34
if you want to test to see if your rules are getting flushed on every load add this code somewhere.
add_action( 'generate_rewrite_rules', function( $rules ) {
var_dump( $rules );
});
Nothing should happen unless you visit settings -> permalinks then you will get a var_dump of the generated rules. If you get it somewhere else then something is wrong.
Also like others have mentioned disable all your plugins or start with ones that might mess with rewriting like a custom post type plugin. See if your problem goes away. Then re activate one by one to find the culprit.
Make sure you flush your rules after deactivating plugins because the broken rules will need to be fixed.