The problem sounds very much like it could be related to this:

This has become a re-occurring problem. The last time it happened I was still getting the odd IM arriving in email but with very different headers.
Original 'reliable' email's first hop:
Received: from lindenlab.com (localhost [127.0.0.1])
by sim3429.agni.lindenlab.com (Postfix) with SMTP id 8F7892B44CD
for <*********@**********>; Thu, 12 Jun 2008 12:50:13 -0700 (PDT)
Message-Id: <20080612195013.8F7892B44CD@sim3429.agni.lindenlab.com>
These emails always had this subject line:
Subject: Message From Second Life
When the problem first emerged 'intermittent' email's first hop:
Received: by web-ds1.lindenlab.com (Postfix, from userid 33)
id 10161768211; Wed, 25 Jun 2008 07:53:53 -0700 (PDT)
Message-Id: <20080625145354.10161768211@web-ds1.lindenlab.com>
These emails had more finessed subject lines:
Subject: Second Life - the object '<object name>' has sent you a message
Subject: Second Life - <agent name> has sent you a message
For a while the emails once again reverted to the original format. What they look like now I have no idea because I don't receive ANY IMs to emails any more.

It wouldn't be a stretch to suppose that Linden have been tinkering with things. Torley Linden seemed to briefly show some interest in the problem but there has never been any kind of acknowledgement.
Someone with more knowledge of email set ups than me might speculate as to what web-ds1.lindenlab.com (as opposed to simxxxx.agni.lindenlab.com) was all about. I'm not sure web-ds1.lindenlab.com even exists any more. At the time of the email headers it reported its IP address as: [64.154.223.153] (helo=web-ds1.lindenlab.com), but just now that IP reports itself as: nat.janus.lindenlab.com
Does anyone have any current IM to email headers? Do they even exist at all?

Note: Janus is the Roman god of gateways, and also lends its name to January (the start of the year) and Janitor (caretaker).