Compound keys and foreign constraints

I am using PostgreSQL 7.4.1 on RedHat 7.2.

The query I am executing is something like (I replaced all the return values
with 'count'):

db=> explain select count(*) from messages m join (select * from
message_recipients r join addresses a on a.Address_Key=r.Recipient where
a.Address='lra(dot)edi(at)edi(dot)cma-cgm(dot)com') as foo on
(m.Message_Key=foo.Message_Key AND (m.Message_Date >= '29-MAR-04') AND
(m.Message_Date <= '31-MAR-04 23:59:59'::timestamp without time zone));

QUERY PLAN
----------------------------------------------------------------------------
----------------------------------------------------------------------------
---------------
Aggregate (cost=75565.60..75565.60 rows=1 width=0)
-> Nested Loop (cost=0.00..75565.60 rows=1 width=0)
-> Nested Loop (cost=0.00..75380.70 rows=61 width=11)
-> Index Scan using addresses_i_address on addresses a
(cost=0.00..6.00 rows=1 width=11)
Index Cond: ((address)::text =
'lra(dot)edi(at)edi(dot)cma-cgm(dot)com'::text)
-> Index Scan using message_recipients_i_recipient on
message_recipients r (cost=0.00..75135.99 rows=19097 width=21)
Index Cond: ("outer".address_key = r.recipient)
-> Index Scan using messages_pkey on messages m (cost=0.00..3.02
rows=1 width=11)
Index Cond: (m.message_key = "outer".message_key)
Filter: ((message_date >= '2004-03-29 00:00:00'::timestamp
without time zone) AND (message_date <= '2004-03-31 23:59:59'::timestamp
without time zone))
(10 rows)

The problem is that the date filter has come up with a couple of thousand
messages out of 350,000 - which is about 10% of what it will grow to. Both
message_key and message_date are indexed.

So, I created a compound index on (message_key, message_date) in the
messages table. I couldn't get it to use the new index no way, no how,
ever, even with a very simple query on exact match on message_key and date.
So I dropped the primary key on (message_key). Now it is using the new
compound key:

db=> explain select count(*) from messages m join (select * from
message_recipients r join addresses a on a.Address_Key=r.Recipient where
a.Address='lra(dot)edi(at)edi(dot)cma-cgm(dot)com') as foo on
(m.Message_Key=foo.Message_Key AND (m.Message_Date >= '29-MAR-04') AND
(m.Message_Date <= '31-MAR-04 23:59:59'::timestamp without time zone));

QUERY PLAN
----------------------------------------------------------------------------
----------------------------------------------------------------------------
-----------------------------------------------------------------
Aggregate (cost=73745.29..73745.29 rows=1 width=0)
-> Nested Loop (cost=0.00..73745.26 rows=11 width=0)
-> Nested Loop (cost=0.00..72011.44 rows=328 width=11)
-> Index Scan using addresses_i_address on addresses a
(cost=0.00..6.01 rows=1 width=11)
Index Cond: ((address)::text =
'lra(dot)edi(at)edi(dot)cma-cgm(dot)com'::text)
-> Index Scan using message_recipients_i_recipient on
message_recipients r (cost=0.00..71776.72 rows=18297 width=21)
Index Cond: ("outer".address_key = r.recipient)
-> Index Scan using messages_i_id_date on messages m
(cost=0.00..5.27 rows=1 width=11)
Index Cond: ((m.message_key = "outer".message_key) AND
(m.message_date >= '2004-03-29 00:00:00'::timestamp without time zone) AND
(m.message_date <= '2004-03-31 23:59:59'::timestamp without time zone))
(9 rows)

And performance is much better. But dropping the original primary key
forced me to drop my foreign key constraints:

NOTICE: constraint $1 on table restored_messages depends on index
messages_pkey
NOTICE: constraint $1 on table message_recipients depends on index
messages_pkey
ERROR: cannot drop constraint messages_pkey on table messages because other
objects depend on it
HINT: Use DROP ... CASCADE to drop the dependent objects too.
db=> alter table messages drop constraint messages_pkey cascade;

Herein lies my problem... I cannot reestablish the foreign key constraints:

db=> alter table restored_messages add constraint "$1" foreign key
(message_key) references messages(message_key);
ERROR: there is no unique constraint matching given keys for referenced
table "messages"

It should be able to use the new compound index, as message_key is the top
index key. There is no date in the subordinate tables to include in the
foreign key reference - it must be on message_key only. If I have an index
on only message_key in messages, then the compound key never gets used and
my search performance takes a nose dive. How do I get there from here?

Wes