User responded to an Outlook 2013 calendar invite and received a message saying it did not reach the recipient

Details of the question are below:

• Office 365 Exchange environment
• Both users using Outlook 2013
• User A sent a calender invite to User B
• User B accepted the invite
• User B then received an error message stating the below:

Your message did not reach some or all of the intended recipients.

  Subject:  Accepted: xxx 
  Sent:     27/10/2015 12:12


The following recipient(s) cannot be reached:

      yyy on 27/10/2015 12:12
            This message could not be sent. Try sending the message again later, or contact your network administrator. The client operation failed. Error is [0x8004010f-0x8004010f-0x000501].

Does anybody have any idea why this may have happened? The two users frequently email each other without issue so I'm not sure what led to this.

Thanks in advance for any help!

I've seen these messages now a few times. It's generated by Outlook - not the server. Usually the case is an out of date Offline Address Book.

You can check this in outlook by first creating a message and then select the recipient from the GAL vs. offline address book, or in OWA (by simply using OWA). If both of these work (which both use the live GAL), it points to OAB.

You can of course force a re-download of the address book to try and correct - but make sure you check BITS server first. If that is not running - you won't download OAB (and thus it's not updated).