Referential actions other than the NO ACTION check cannot be deferred, even if the constraint is declared deferrable.
and
NO ACTION
Produce an error indicating that the deletion or update would create a foreign key constraint violation. If the constraint is deferred, this error will be produced at constraint check time if there still exist any referencing rows. This is the default action.
You might try INITIALLY DEFERRED instead.
The functionality has been in there since 7.4 at least, so I doubt that it isn't working.