Novice schema question

I have a bit of a stumper.

I'm writing an IMAP server. The goal it to achieve IMAP scalability by
allowing a user to set up a fleet of thin servers to speak IMAP and push
the scaling problem to the SQL layer (where the problem has been largely
solved). This means I want to write it with PostgreSQL, but I want it to
wind up being portable to whatever big iron someone might want to use.

The rules (that matter for this discussion) are

Mailboxes are unique.
Messages are unique.
Messages must be in at least one mailbox.
Messages may be in multiple mailboxes.
Messages have headers and body parts and lots of other things (FOREIGN
KEY Messages ON DELETE CASCADE).

So I end up with mailboxes, which have a primary key that is a mailboxid.

I also end up with a message table, which has a primary key that is a
messageid, but nothing else (the contents of a message are headers and
body parts which are in separate tables because they are 1-to-many).

There is a messagemap which relates messages to the mailboxes.

With cascade deletes I can arrange for the deletion of a mailbox to
delete all its message map entries and for the deletion of a message to
delete its message map entries, headers and body parts.

The only trick left is to arrange for a message to be deleted when its
last messagemap entry is deleted.

The messagemap messageids can't be the primary key for messages, because
there can be multiple entries in the message map for a single message
(because it can be in multiple mailboxes).

The only solutions I have found so far suck:

One is to create an after delete trigger for the message map to delete
the message if it no longer has message map entries. This winds up being
non-portable (I wrote it in plpgsql: SELECT INTO c COUNT(MessageID) FROM
MessageMap WHERE MessageID=OLD.MessageID; IF (c=0) DELETE FROM Messages
WHERE MessageID=OLD.MessageID; END IF;).

The other is to tell the users to set up a cron job that does

DELETE FROM Messages WHERE NOT EXISTS (SELECT MessageID FROM MessageMap);

which is silly because it just seems to me I ought to be able to just
have the database *do* stuff like that for me.

If I go to all this trouble, then the act of

DELETE FROM Mailboxes WHERE MailboxID=4792;

will also delete all of the message map entries and (for non-shared
messages) all of the messages as well.