My first guess is that your htaccess file is being changed. I’d look at that file content and time stamp after the 404 happens. (Although it is possible to make changes to a file without changing the file’s time stamp – I’ve seen it done on a hacked site.)
Redoing the permalink settings rewrites the htaccess file, which is why I suggest looking there.
You might also do a search of all plugin’s code for ‘htaccess’ to see if there is code that is directly changing that file. There might also be a filter that can be called to reset permalinks but can’t find it right now.
You might also consider that perhaps your site has some malware. There are many googles/bings/ducks on how to figure that out.