Laiv suggest that this is a question to be answered by the business expert (domain experts or business analysts), which is the correct approach in my opinion.
My answer is somewhat theoretical; it may have neglected some of the fine points that OP has explained.
One thing is certain. Given the current capabilities and limitations of Microservice1 and Microservice2, Referential integrity (link to Wikipedia) cannot be maintained at all times.
(Throughout this answer, client / proxy / gateway are used synonymously.)
There will be gaps in time, whether during normal operations (creation of A, B, C all succeeded), or during unsuccessful operations (at least one of them failed during creation), where a different client other than yours will be able to see non-existent or broken links between these microservices, if they have direct access to these microservices.
A simple way to avoid exposing any clients to any invalid references is to create each object on each microservice first, without providing any external IDs. Only after all objects are created successfully, then each object will be updated with relationship IDs. Given the simplicity of this approach, I think in most cases this will be the approach chosen by most programmers.
One typical approach used to partly mitigate the consequences is to give each client the ability to create IDs and their relationships ahead of time, before the actual objects are created in their respective space. A typical implementation choice is to use UUID (GUID) for everything. That way, each object can be created with a new ID with low (practically but not theoretically zero) probability of collision, and it can be associated with the IDs of its related objects even though those related objects haven't been created in their respective microservices.
One other approach used to mitigate the temporary break in referential integrity is to require all clients to implement timed retry. If a client tries to access an object on Microservice1 via a UUID that was conveyed through a property returned from Microservices2, and if Microservice1 says that it has no knowledge of that UUID whatsoever, it is required that the client wait for a small amount of time and then try again.
Another mitigation that is used to complement the above is to require all newly created or updated objects that contain IDs to external systems to "restore their referential integrity" within a predefined deadline. For example, if an object has a new external UUID added, there will be an agent running on the same microservice that validates that external UUID after a certain period of time (e.g. 5 seconds, YMMV). If the external UUID is not valid, it is flagged for some post-processing or exceptional handling. In general, this validation does not happen immediately. Thus it is not the responsibility of the REST API to return a result code if the UUID is correctly formatted but is invalid on a different microservice.
Yet another approach is to have one centralized object graph relational microservice. All relations between A, B, C would be recorded on this centralized microservice; A, B, C will simply store what each is supposed to contain.
There are many more approaches out there.
The referential integrity issue can only be mitigated; there is no true solution that completely eliminates the issue. Anyone implementing on this system has to know how to apply these mitigations.
Finally, use of gateway is strongly recommended. A gateway is the only way to ensure that the creation of UUIDs are correctly randomized. If arbitrary clients are allowed to specify UUIDs which are actually non-random (e.g. intended to create collisions, or even using the same UUID to abuse the API and cause a DoS), it can open the system to attacks.