Another SysAdmin here having the same problem, cannot send any email to addresses using MessageLabs/Symantec. Our server IP is completely clean and locked down, not on any blacklists, using DKIM signing and SPF. Very frustrating, what a horrible service Symantec is.