If you want the backstory on my dealings with issues like this with Barracuda (or probably any email security service that routes mail internally versus doing an MX lookup) check out my original post on this sort of thing.
I wanted to do this quick post as I noticed that there were not a lot of references to 550 5.7.51 while doing my initial troubleshooting. I knew that my customer (the sender) did not have any connectors or rules set up when emailing the recipient domain in question, and this problem cropped up within only a couple days of enabling outbound mail scanning at Barracuda. 2+2=4 sort of thing.
So, I made my first call to Barracuda rather than Office 365. The engineer I spoke to was thinking that the recipient domain might actually have some kind of connector set up, but then I mentioned the possibility that they might have this domain listed and verified with Barracuda ESS and that the messages might have been internally routed. That was key to expedite the solution. He was able to confirm my suspicions and set the recipient domain to a status of “new” in their system, which apparently causes Barracuda to lookup and route mail to the recipient domain’s MX record. Problem solved.