The isDeleted flag is good because it gives the appearance that the data is gone, without removing the context of the data itself.

Immutable facts are great if you want to:

1) Avoid a large amount of updates/race conditions on your tables. Immutable facts, being immutable, can be done using purely inserts.

2) Want to keep a trail or context to the data you're storing. This has a benefit of keeping a log that you can later use to trace issues, behaviours or generate statistics. If you're keeping a state in a database column, without external logs you aren't able to check when or why that state changes. Immutable facts keep track of this for you, but require quite a bit more overhead.

I've always hated "isDeleted" flags because it adds something that you have to remember to every query you write.

I would almost prefer some way to "ghost" a row where without a specific switch the DBMS will never return it from a query.

With a view and a set of rules, you can do such things in Postgres, without your application noticing:

http://www.postgresql.org/docs/9.2/static/rules-update.html

I might be trivializing this but you could create a view "ActiveUsers" / "DeletedUsers". Not saying this make the IsDeleted flag perfect, but it would alleviate that particular problem, IMO.