I have been struggling to resolve “List does not exist. The page you selected contains a list that does not exist. It may have been deleted by another user” error for the past 48hrs.
Situation: One of my client whose site I had setup recently started getting the above error. The error occurred when editing a view or modifying an existing view of a document library or a list. The site was accessed internally over http and externally over https. This error occured only when accessing the site over https and not via http. Before you think ahhhh dumb nerd it was AAM let me tell you my readers I have been with SharePoint before AAM was THE word. The users had not removed any list template or site template and the troublesome thing was that this error did not appear on the top level site elements.
ULS logs didn’t help, shifting and juggling between AAM zones didn’t help, SharePoint publishing feature on and off didn’t help, changing site for SharePoint groups and even to the extent adding all Domain Users as site collection admins didn’t help (Exterme I know).
Resolution:
1. Login to your server and open IIS.
2. Click on the https site, probably this be the site running on port 443.
3. In the IIS site options click on HTTP Handlers.
4. Look for OwssvrHandler, Right-click and select Edit Feature permission and make sure that Execute option is selected as shown below. Click Ok.
5. Restart IIS and you should be on your way.
SharePoint cocktail 
All settings are correct, but still no luck. Any other idea?
Thank you very, very much! Everyone else was pointing to AAM as the source of the problem. Your solution fixed my problem!
I had the same error after an upgrade from Sharepoint Server 2007 to Sharepoint 2010. The original site was built on the “Site Directory” site template which by default includes “Search”, “Reports”, “Documents”, “Site Directory” and “News” subsites. We only use the “Site Directory” subsite and I noticed that the same error as above came up when I selected the “Reports” site. After I deleted all these subsites (except the “Site Directory”) my “Site Administration > Site Content and Structure” works again!