How do OIDs solve this? Updating a record it still updating a record. OIDs don't magically make that problem go away.
One solves this problem the way one solves any other data problem: logical thinking and planning ahead. If you are creating a long-running business application where things like addresses may change, you design your database to take that into account. You store a timestamped address with every order record, or you store multiple addresses by date range. It's not exactly rocket science.
There is literally no reason to use OIDs except as a crutch when one has created a table without a primary or candidate key--and even then OIDs won't save you from bad logic, such as duplicate records or other idiocy.
BTW, it is important to also remember that OIDs are not enabled by default for new table creation. Many times the PostgreSQL core team has discussed whether to deprecate OIDs completely. The decision was made to keep them for two reasons: a) some applications still depend on them, however misguided their reasons and b) Some PostgreSQL add-ons and external solutions (replication, etc...) use them.