We have a stage server set up where we use CI with TeamCity. At every commit the site is rebuilt ie we clean out the files and copy in the files from the build. We have all config files etc in VCS so that's not the problem, because the site works but the EPiServer UI only returns a 404! We don't clean out the AppData-files, but parts of it is in the VCS.
In the beginning I could solve the problem by copying my local files in /modules, /modulesbin and the AppData to the server, but now that doesn't work anymore.
Version of EPiServer is 7.6.5 and the UI is 7.7.0.
In that version you have these files in the directory modules below the root of the site and in that directory there is a directory called _protected. Do you have these with the deploy?