I agree that it’s legal - I just don’t think it’s a good thing to do. I also think that snooping on your employees (even if you tell them that you’re doing it) is probably not the best way to show them that you trust them.
Also, you’re putting a whole lot of (probably sensitive) information in one place. Agreed, if someone has privileged access to the server or network, they could probably obtain most / all of the same information, but keeping it around seems like a bit of a risk. When you’re talking about letting an outside company (e.g., us) handle this information, you’re opening up an even bigger can of worms.
In any event, it’s not really possible for us to do this on a per-domain basis, at least not without using some sort of ugly hack, and we do not maintain this sort of information globally either (other than the usual logging information; envelope-senders and envelope-recipients, client IP addresses, etc.). But, as I mentioned, doing something like this locally probably wouldn’t be too difficult. With Postfix, you can just specify an “always_bcc” address / user in main.cf. I’d assume that other MTAs have similar facilities.
Just be sure to be careful about it - encrypt (and archive) the file periodically, don’t keep the encryption key on an internet-connected machine, limit access and root / administrator access to a small group of people, make sure to notify employees that their messages are being monitored, etc.