PostgreSQL today is finally deprecating the OID feature they inherited from the original Postgres code. The OID used to be an implicit row ID that would have these problems.
The OID is generated from a sequence shared by all databases in the "cluster" i.e. the PostgreSQL server instance. So it is not only non-deterministic based on insert orders to your DB, but also is affected by inserts in other databases on the same server.