Doubtless you're aware of the 'Auto-load' checkbox next to the list of plugins in the Plugin Manager window... so it seems those are getting un-checked somehow when you turn off Maya? Strange.
There is a preferences file which is supposed to store this information. It will be called 'pluginPrefs.mel' and stored in your version of Maya's preferences directory by default (e.g. maya/2012-x64/prefs/).
The contents of the file will look something like this:
And so on, one line for each plugin. Take a look at that file, and see if there are any clues as to what's going on. Also make sure you have permission to overwrite that file, since that's what Maya should do whenever you save preferences or shut it down. (Check the timestamp on the file.)
Hope that points you in the right direction of finding a solution!
FBX maya is the only one I've turned back on so far, so that makes sense. But it's good to know that there is a file storing these preferences. A nice backup containing all regular plugins should do the trick when it happens again.
Would you know which plugins Maya has turned on by default? I only know a few; obj exporter, fbx, mayatomr.