I had this exact issue and after trying to error_log(...) everything related to flush_rewrite_rules(...) and ruling out all the plugins and Cron jobs within Wordpress, I started looking outside of the Wordpress admin interface.

I found in the web hosting control panel (CPanel) there was a section called WordPress Management > WP Toolkit that was connected to the Wordpress installation. I found in these logs that this was performing daily maintenance at the exact time the permalinks were being broken.

By detaching the Wordpress installation from the WP Toolkit, the problem was resolved.