Sending email isn't processed by Google Apps though, only incoming. We have a dedicated email server that handles outgoing mail. Sorry about the issue though and I would love to take another look at the problem directly. Some edge cases come up that take some pretty deep digging to find out what's wrong between the main email server and the setup on the users end, but that's typically pretty rare. I've only had that happen on a few isolated instances.