In to have the right context for the more specific answers to your question, it is important to understand what the purpose of "private APIs" really are:
To understand it we must know what an API (Application Programming Interface) is: An API is something that allows the developer of applications to invoke functionality implemented by someone else. Historically, you had system programmers creating operating system and system libraries, and you had application programmers creating the application that end-users would use. The link between them would be the API.
Today, APIs exists in many different forms that serves different purposes:
Operating System APIs: For example the use of "system calls" that allow non-operating system programmers (i.e. user-space programs) to invoke functionality within the operating system kernel. On most common operating systems this is also a security boundary (i.e. this is the place where checks and controls are in place to ensure that only permissible functionality is invoked)
System Library/Framework APIs: For example the system vendor supplies a framework for creating user interfaces so that the whole system can have a set of recognizable widgets (such as buttons, lists, etc) that are drawn the same way across applications. There's usually no security boundary here.
Application Internal APIs: Some applications are internally divided into libraries/frameworks and feature their own APIs. It might be for example an application developed by multiple teams that divide up their areas of responsibility through libraries/frameworks - or it might be that a library is created once and used for many different applications while the developer wishes that code to remain separated for the sake of maintainability. The library might be in-house developed or it could be an open-source library shared by thousands. There's usually no security boundary here.
Network / Web APIs: Some systems expose APIs through networks, or more specifically through the web. For example Amazon exposes an API that allows developers to send a photo from their app to Amazon's servers, and receive an OCR'ed version back (i.e. text extracted from the photo). There's usually a security boundary here, as these web APIs commonly require some form of authentication to ensure payment or protect private information.
Now that we have the basics of APIs down, next up is what a "private API" then means:
In fact, Apple doesn't refer to "private APIs" as such. Instead they publish developer documentation that includes API references and header files, and they then recommend that developers only use those publicly documented APIs. So called "private APIs" are what Apple actually calls "non-public APIs".
It is not an Apple invention, but rather private/publics APIs have been used in the industry for decades. For example historically Microsoft would publish extensive developer documentation on how to use their Windows USER API for creating graphical user interface with various controls, but their Office product would have private controls that were only available in Office even though they existed in a API that third-party developers technically could have used.
And now we come to the purpose of "private APIs":
Traditionally public APIs comes with a (sometimes implied, sometimes explicit) promise that these APIs would not disappear or change underneath application developers for a long time. A developer could use a public API and expect it to perform as documented - and to keep doing that when the vendor released minor and major updates. Usually the developer could also expect to get a warning (a so called deprecation notice) when the public API they were using would change or go away in the following years. Similarly developers would expect to be able to report bugs in these APIs to the vendor.
Private APIs on the other hand did not enjoy these niceties. A private API could disappear in a system update, their could suddenly start working differently (or not at all) - and developers would not be able to complain to the vendor about bugs or missing features.
This is also how public/private APIs worked on the iPhone in the beginning. The reason that many think of iOS when you mention "private APIs" is that Apple later introduced a new requirement for publishing an app on their App Store - namely that the app should only use public APIs. This way Apple is more able to ensure themselves that an app that worked last year would keep working next year for the customers that bought them from the App Store.
You might assume that the distinction between "public" and "private" APIs to have something to do with system security. That's almost never the case. In many cases APIs are in the form of executable located in a library/framework file on the system. There's nothing technically hindering the developer from just copying code from the "private" library into their own application making it part of their application and thus no longer an API. Depending on how much code is copied, the developer would be infringing on copy rights and possibly a license agreement between them and the vendor.
In reality, private APIs are often made private because they're still changing. For example Apple might have a private API for a new piece of hardware or a new set of functionality on their device. With each release that API changes a bit as Apple developers learn from mistakes and discover the way user's interact with their own apps that use these functionalities. Later when the API has stopped changing (as much), Apple makes that same API public as now they think it is ready for consumption by third party developers.
Now we get to your more specific questions:
Part of the reason Apple (and other vendors) do not strip out the
private API symbols from their libraries is mainly that then they
themselves, or partners they have allowed to use private APIs, also
would not be able to readily use such these APIs in their apps.
Apple would then have to duplicate all libraries - having a version
for themselves and another for non-partners, and ensure that the
right version was made available in each case.
A more logical way for Apple to restrict the use of private APIs
would be to change the dynamic linker and the messaging system
between objects used in Objective-C and Swift to ensure that
non-entitled apps would be blocked from calling private APIs.
However in addition to adding lots of really unnecessary complexity - it would come with a non-trivial performance penalty.
In actual fact, Apple is probably not that concerned about a
developer using a private API - and thus they stick to simply having
a guideline, trying to detect the most obvious uses to educate
developers, and then only do something about it should it become
publicly known that a private API has been used.
In almost every case, the use of a private API could have been
replaced by the app developer by simply copying the executable code
from the library into their own app - thus making the whole point of
contention moot. The reason developers use private APIs is often to
access functionality that Apple built that they do not have the time
to recreate themselves, or to access functionality that they expect
will be public anyways soon. It then becomes the responsibility of
the developer to ensure that they only use that private API for
certain versions of the system that actually has that private API -
and they would endure a risk of their app breaking with system
updates.
Regarding the Uber case: The real problem here is actually not the use of private APIs. It is actually a security bug in the operating system that private information was exposed to the app. The app developer could just have done the same thing in their code as the private API did and they could have gotten access to the same private information. That is not good.
Yes, automated scanning is a "cat and mouse" game - where it is usually much easier for the app developer to make something that obfuscates their use of private APIs, and much harder for Apple to build a detector for. I don't think the use of private APIs really is that much of a "problem" for Apple.
