The requested resource does not exist [error] in Salesforce. What is wrong with Salesforce?

Based on your error description and screenshot, I assume that you're doing it through programetically ( Apex, Python, Java...) and there is no time delay between your first request(extraction of data, /Query?q=) , response and the second request (details of the record based on ID, /sobjects/ObjectPermissions/{id})

1. The records with '000' can be idntified as EmptyKeys in Salesforce and generally refers to null relationship values.

Contact is the lookup field on Opportunity and below queries will return the same count.

SELECT count() FROM opportunity WHERE contactId = null
SELECT count() FROM Opportunity WHERE contactId = '000000000000000AAA'

2. In reference to the records in Object permission (starting with '000'), is little different from Empty keys and breakdown of the ids can be found in the blog

Mystery Behind The Salesforce Key Prefix '000'

3. In the above scenario, we can't filter out these objects in Metadata API query, however we can filter the records before sending out the second request in APEX code.

Set responseIds - Response record Ids returned from First Request and process the Ids to filter out '000' Ids for second request.

String prefix = Schema.SobjectType.ObjectPermissions.getKeyPrefix();
for(String str : responseIds){
    if(!str.subString(0,3).contains(prefix)){
        responseIds.remove(str);        
    }
}

4. RecentlyViewed object is not to be used directly. The IDs in this object are not ID belonging to the recentlyViewed Object, instead they are actual record ID's. So if you intend to access the records from this object, you need to fetch the Ids from recentlyviewed Object then decode the keyprefix to get the proper sObject Name then use it this manner /sobjects/{decodedSobjectName}/{ID}

Or alternatively you can use /services/data/v48.0/recent (refer Salesforce documentation for details)

https://developer.salesforce.com/docs/atlas.en-us.api_rest.meta/api_rest/resources_recent_items.htm

5. Although we have separate object for each standard picklist, they all share same keyprefix/objectType. The following code will remove all the request which are directed towards picklist objects (Taskstatus, Casestatus, solution status...)

   for(Id str : responseIds){
        if(Id.getsobjecttype() == 'Picklistmaster'){
            responseIds.remove(str);        
        }
    }
   

6. As for Loginhistory, the records later than 6 months will be deleted internally by salesforce. So if you run the 2 request (Query request, later data request) and if this 2 request happens to lie between the Salesforce maintenance window, then during your second request the id referred is already deleted from the org, hence the error. And make sure you have Manage Users permissions.

TL;DR - I wouldn't worry about these.

1. That Id looks fake. There's no proper object that has 000 key prefix. (there are lots of blog posts about "known key prefixes" on the net but pay attention to the timestamps, new objects are added with pretty much every release so content can get outdated). ObjectPermissions should be prefixed with 110.

   Id i = '000000003guy001AAA';
   System.debug(i.getSobjectType());
   // System.SObjectException: Cannot locate Apex Type for ID: 000000003guy001AAA
   

   Daniel Ballinger's blog post is ancient but great compilation: http://www.fishofprey.com/2011/09/obscure-salesforce-object-key-prefixes.html. He does list an entry for key "000" and it points to his another post: http://www.fishofprey.com/2011/06/salesforce-empty-key-id.html

2. The tables you have listed are real tables "but" most of them are for internal housekeeping, they're "picklists on steroids".

   CaseStatus deserves it's own table because changing status has side effects of marking case closed. PartnerRole is special because it includes reverse partner roles for bidirectional mapping. You can't really grant Read/Create/Edit/Delete rights to these, at least not with what ObjectPermissions is about. This would be checkboxes on Profile / Permission Set but most of them would be covered by "Configure Application".

   Do you have same issue with OpportunityStage or CampaignMemberStatus?

3. LoginHistory isn't a picklist but probably protected by "Manage Users", EntityDefinition hm... probably "View Setup and Configuration".

4. My gut feel is SF includes these entries for completeness but they are blank if the parent profile / permission is special. Permissions can be always enabled (System Administrators, any other profile with "Modify all data" & "Author Apex" probably too) or always disabled (blocked by license for example). By block I mean situations like customer community license - there's no way you can grant access to Opportunity or Lead - the checkboxes simply aren't there. Similar with Platform User (access to 10 custom objects only), Chatter Plus license (or whatever is the correct name). So if there's no way to change it - why bother giving it a real id.

   What do you get when you run this?

   SELECT Id, SobjectType, Parent.Profile.Name, PermissionsRead
   FROM ObjectPermissions
   ORDER BY Id
   

Yes, it's bit weak explanation but remember that ObjectPermissions and FieldPermissions are still relatively new. The one source of truth is viewing Profiles as XML (metadata API) or running "describe" calls (Apex, SOAP API, REST API - only for current user). FieldPermissions doesn't have entries for all fields on the object (Id, CreatedById, SystemModstamp...) and nobody complains. These queryable objects are a shortcut but they have limitations.

Based on the error response and your description, it looks like a faulty connection between the client you're using (Workbench?) that's trying to access your Salesforce Org. This is how I would approach troubleshooting-

1. Check to see if this is an issue specific to an external client (Workbench) as compared to requesting the data elsewhere (DataLoader, VS Code, Dev Console/internal access). If you can access it via other methods then you can confirm it's this specific connection to your org.
2. Confirm Profile/Permission Set access to Objects and Fields (sounds obvious, but you'd be surprised). Even individual field-level access can disrupt you retrieving a record (even if you're a System Administrator, this doesn't mean you always have Field Level Security to every single field).
3. Confirm that your running user on the client has full sharing access to the records you're requesting. This is especially important to check if some records return for a query on an object, but not all of them.

I'd have to get more detail to help further, but confirming details on the above would go a long way. The main point is that if you can access certain records within an object, but not others, then it tells me that you have authentication to the org, have object access, but perhaps don't have full sharing or field level security access for that particular running user.