More aggressive than SJW's, even.
(SJW = SOCIAL JUSTICE WARRIOR, SERIOUS YOU GUYS!!!)
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.
I wouldn't even recommend bothering with hstore. There are several even better ways to use Postgres in a "NoSQL" setting.
For example there is the Mongres project, that lets a PostgreSQL database emulate the MongoDB protocol. So you could literally drop Postgres into a Mongo-powered application with not a single hiccup, and get a) better performance and b) all the back-end relational stuff you need when it comes time to do reporting or other business logic.
There's also the new JSONB datatype in PostgreSQL 9.4, which I would recommend over hstore if you want to just store "free-form" data in records.
EnterpriseDB did a very well-thought-out study on PostgreSQL/NoSQL.
That's not even close to what "referential integrity" means. In fact, it could be used to accomplish quite the opposite.
OIDs are one feature of PostgreSQL that should be buried inside the implementation and not allowed to be accessed from the developer side. Otherwise you are pretty much completely going around the whole point of the Relational Model. If you are developing an application in such a way that it needs pointers to rows, you might as well just store data on the filesystem and be done with it. Or use one of those fancy NoSQL thingies and enjoy your data corruption.
All the simple programs have been written.