Unique across tables
To enforce unique email addresses, I would remove all competing email columns and store them in one central email table for all active emails. And another table for deleted emails:

CREATE TABLE users (
  user_id  serial PRIMARY KEY
, username text UNIQUE NOT NULL
, email    text UNIQUE -- FK added below  -- can also be NOT NULL
);

CREATE TABLE email (
  email    text PRIMARY KEY
, user_id  int NOT NULL REFERENCES users ON DELETE CASCADE
, UNIQUE (user_id, email)  -- seems redundant, but required for FK
);

ALTER TABLE users ADD CONSTRAINT users_primary_email_fkey
FOREIGN KEY (user_id, email) REFERENCES email (user_id, email);

CREATE TABLE email_deleted (
  email_id serial PRIMARY KEY
, email    text NOT NULL  -- not necessarily unique
, user_id  int NOT NULL REFERENCES users ON DELETE CASCADE
);


This way:


Active emails are unique, enforced by the PK constraint of email.
Each user can have any number of active and deleted emails, but ...
Each user can only have one primary email.
Every email is always owned by one user and is deleted with the user.
To soft-delete an email (without losing it and its affiliation to its user, move the row from email to email_deleted.


The primary email of a user cannot be deleted this way, because the primary email must not be deleted.

I designed the FK constraint users_primary_email_fkey to span (user_id, email), which seems redundant at first. But this way the primary email can only be an email that is actually owned by the same user.
Due to the default MATCH SIMPLE behavior of FK constraints, you can still enter a user without primary email, because the FK constraint is not enforced if any of the columns is null.
Details:


Two-column foreign key constraint only when third column is NOT NULL



The UNIQUE constraint on users.email is redundant for this solution, but it may be useful for other reasons. The automatically created index should come in handy (for instance for the last query in this answer).

The only thing that's not enforced this way is that every user has a primary email. You can do this, too. Add NOT NULL constraint to users.email

UNIQUE (user_id, email) is required for the FK constraint:


How does PostgreSQL enforce the UNIQUE constraint / what type of index does it use?


You have doubtless spotted the circular reference in the above model. Contrary to what one might expect, this just works.

As long as users.email can be NULL, it's trivial:


INSERT user without email.
INSERT email referencing the owning user_id.
UPDATE user to set it's primary email if applicable.


It even works with users.email set to NOT NULL. You have to insert user and email at the same time though:

WITH u AS (
   INSERT INTO users(username, email)
   VALUES ('user_foo', 'foo@mail.com')
   RETURNING email, user_id
   )
INSERT INTO email (email, user_id)
SELECT email, user_id
FROM   u;


IMMEDIATE FK constraints (the default) are checked at the end of each statement. The above is one statement. That's why it works where two separate statements would fail. Detailed explanation:


How to deal with mutually recursive inserts


To get all emails of a user as array, with the primary email first:

SELECT u.*, e.emails
FROM   users u
     , LATERAL (
      SELECT ARRAY (
      SELECT email
      FROM   email
      WHERE  user_id = u.user_id
      ORDER  BY (email &lt;&gt; u.email)  -- sort primary email first
      ) AS emails
   ) e
WHERE  user_id = 1;


You could create a VIEW with this for ease of use.
LATERAL requires Postgres 9.3. use a correlated subquery in pg 9.2:

SELECT *, ARRAY (
             SELECT email
             FROM   email
             WHERE  user_id = u.user_id
             ORDER  BY (email &lt;&gt; u.email)  -- sort primary email first
             ) AS emails
FROM   users u
WHERE  user_id = 1;


To soft-delete an email:

WITH del AS (
   DELETE FROM email
   WHERE  email = 'spam@mail.com'
   RETURNING email, user_id
   )
INSERT INTO email_deleted (email, user_id)
SELECT email, user_id FROM del;


To soft-delete the primary email of a given user:

WITH upd AS (
   UPDATE users u
   SET    email = NULL
   FROM   (SELECT user_id, email FROM users WHERE user_id = 123 FOR UPDATE) old
   WHERE  old.user_id = u.user_id
   AND    u.user_id = 1
   RETURNING old.*
   )
,    del AS (
   DELETE FROM email
   USING  upd
   WHERE  email.email = upd.email
   )
INSERT INTO email_deleted (email, user_id)
SELECT email, user_id FROM upd;


Details:


Return pre-UPDATE Column Values Using SQL Only - PostgreSQL Version


Quick test for all of the above: SQL Fiddle.