Maybe this is SPAM mail? Do you have a decent filter in-place? If not, look at MessageLabs.com....
Also, empty TO/CC/FROM fields in Emai Headers are against Request For Comments, in particular,
RFC 2821 which may mark you mail as corrupt.
This looks more like an email server issue than Enterprise Vault balking.....
Ta,