Ephemeral external IP addresses: these addresses are available to VM instances and forwarding rules. Ephemeral external IP addresses remain attached to a VM instance only until the VM is stopped and restarted or the instance is terminated. If an instance is stopped, any ephemeral external IP addresses that were assigned to the instance are released back into the general Compute Engine pool and become available for use by other projects. When a stopped instance is started again, a new ephemeral external IP address is assigned to the instance.
I have thought is instantaneously and we won't be getting back the same ephemeral IP address once the VM is stopped. However, it seems that ephemeral external IP addresses will still be assigned to a project for a while longer. For instance, I deleted a VM and released an IP address two days ago. The same IP address is assigned to a new VM today.
How long does it take to release the ephemeral IP addresses back to the GCE pool?
Are the ephemeral external IP addresses "assigned" to VPC or Project? If one has multiple projects within a VPC, will the ephemeral IP addresses be rotated within the projects until they are released to the GCE pool?
The answer is "it should not matter if ephemeral addresses are reused for your instance or not".
There is no guarantee that your instance will obtain the same address or will not obtain the same address. If you are designing something that depends on a certain ephemeral IP address behavior, your design will fail at some point.
Your question quotes Google's official ephemeral IP address policy. Design to that statement and do not depend on environment level behavior.
If you require a fixed IP address, then assign your instance a static IP address. Otherwise, your instance will have whatever address Google Cloud decides, which may or may not be the same address between restarts or recreates.
If your goal is to randomize public IP addresses, then you cannot count on the ephemeral address behavior to implement that. You can allocate a set of static IP addresses and then change which one is assigned to an instance. Note that unused IP addresses are billed (not free). Another method is to create instances in different regions and zones which will have different public IP addresses. You also could write a script to create VMs until the address is different (not part of a previous set of addresses) and then delete the other VMs (subject to quota restrictions).
From a customer support perspective, it is to Google's benefit to reallocate the same address to you. This minimizes a common problem. Some customers do not understand that the default IP address is ephemeral and what that means. They reboot their instance and the IP address changes. That breaks their SSH scripts, DNS settings, etc. The ephemeral address behavior cannot be consistently deployed but is a positive where possible.