Many to many link tables with history?
From Erwin's suggestion above about using a tstzrange exclusion constraint, this seems to have the desired effect:

Firstly, as the admin user postgres I had to execute this CREATE EXTENSION btree_gist on the target database (PostgreSQL 9.2.3 on OpenBSD).

Then as the database user:

CREATE TABLE subscribed_dns_domain
(
  subscription integer NOT NULL,
  dns_domain integer NOT NULL,
  active_period tstzrange NOT NULL DEFAULT tstzrange(now(), NULL::timestamp with time zone, '[)'::text),
  customer_add_reference character varying(40),
  customer_delete_reference character varying(40),
  CONSTRAINT subscribed_dns_domain_pk PRIMARY KEY (subscription, dns_domain, active_period),
  CONSTRAINT subscribed_dns_domain_dns_domain_fk FOREIGN KEY (dns_domain)
      REFERENCES dns_domain (id) MATCH SIMPLE
      ON UPDATE CASCADE ON DELETE RESTRICT,
  CONSTRAINT subscribed_dns_domain_subscription_fk FOREIGN KEY (subscription)
      REFERENCES subscription (id) MATCH SIMPLE
      ON UPDATE CASCADE ON DELETE RESTRICT,
  CONSTRAINT subscribed_dns_domain_single_active_ek EXCLUDE 
  USING gist (dns_domain WITH =, active_period WITH &amp;&amp;)
)


New subscriptions to domains are easily added:

INSERT INTO subscribed_dns_domain (subscription, dns_domain) VALUES (2, 4);
INSERT INTO subscribed_dns_domain (subscription, dns_domain) VALUES (2, 5);
INSERT INTO subscribed_dns_domain (subscription, dns_domain) VALUES (3, 6);


With it baulking on duplicate domain names with overlapping subscription time ranges (as desired):

INSERT INTO subscribed_dns_domain (subscription, dns_domain) VALUES (2, 6);

ERROR:  conflicting key value violates exclusion constraint "subscribed_dns_domain_single_active_ek"
DETAIL:  Key (dns_domain, active_period)=(6, ["2013-10-10 20:43:55.891139+01",)) conflicts with existing key (dns_domain, active_period)=(6, ["2013-10-10 20:11:48.54009+01",)).
********** Error **********


Subscriptions are easily ended:

UPDATE subscribed_dns_domain
SET
    active_period = tstzrange(lower(active_period), now())
WHERE
    subscription = 2 AND
    dns_domain = 4 AND
    upper(active_period) IS NULL


Active subscriptions are easily found:

SELECT
    subscription,
    dns_domain
FROM
    subscribed_dns_domain
WHERE
    upper(active_period) IS NULL

 subscription | dns_domain
--------------+------------
            2 |          5
            2 |          6
(2 rows)


As is historical data:

SELECT
    subscription,
    dns_domain,
    lower(active_period) AS added_at,
    upper(active_period) AS deleted_at
FROM
    subscribed_dns_domain
WHERE
    upper(active_period) IS NOT NULL

 subscription | dns_domain |           added_at            |          deleted_at
--------------+------------+-------------------------------+-------------------------------
            3 |          6 | 2013-10-10 20:10:14.269551+01 | 2013-10-10 20:11:33.467619+01
            2 |          4 | 2013-10-10 20:10:09.611487+01 | 2013-10-10 20:48:15.64681+01
(2 rows)