Well recruitment@domain.co.uk and recruitment@domain.onmicrosoft.com are two different addresses, so it's not necessarily true that that shared mailbox has them both. The easiest way to find which object has the address is to run the Get-Recipient cmdlets against it:
Get-Recipient recruitment@domain.co.uk
Make sure to also check for Group mailboxes, which are excluded by default:
Get-Recipient recruitment@domain.co.uk -RecipientTypeDetails GroupMailbox
Or do the same against the legacyExchangeDN value you get from the error message. As you didn't specify where you are creating the shared mailbox, it's best to check both O365 and the local AD.
