I've deleted and re-created an addressbook and everything went fine, 
so if you don't have the same problem with objects belonging to a 
non-existent share, then it must have been a problem during one of the 
numerous migrations or an admin error.
I can see several accounts with the same problem.

Yes, it's the main address book, named "user@domain.tld's Address Book"

It's registered as a share with a randomised id, but all entries in 
turba_objects are listed with the owner user@domain.tld. I also see 
that the share's owner does not exist in sharesng_users, but that 
doesn't seem unusual.

The 2nd source I see in Turba is properly registered as a share and 
all entries in turba_objects are using that share name as the owner.

Do you have this magic address book showing in Turba's "address book" 
prefs? Is it selected?

I've just added a contact to that "special" share and it syncs with 
devices, so I'm guessing its registered and working properly, but it's 
not associated with the proper share_name.
If I want to share it via CardDAV, I see the id/name of the empty addressbook.

I dug deeper and here is what I found.

I have 2 sources in Turba.

The connector returns 2 sources, however one of them is empty. That's 
what is used for the query and there is no public cert, so that part 
of the behaviour is correct.

I've checked the turba tables and there are 3 sources (owner_id) in 
turba_objects.
The 2 first ones (seens by the connector) have a randomised name, but 
the 3rd one is named user@domain.tld.
That source does not exist in turba_sharesng
That source is the main one being used by turba and that's where the 
cert has been saved.

It could be that something is broken here, but how come Turba is using 
something which does not exist in sharesng as its main source?

It's been partially filled with some data from a phone, so it must 
have been syncing at some point as well.

This works for me without any issue. Does the Horde log show the 
expected turba queries for the user you are looking up?

When adding a recipient in an email I want to encrypt, the iOS device 
queries the server, but can't find any certificate.

I'm trying to send an email to myself.
Turba has an entry with my email address and the "S/MIME Public 
Certificate" field has my public key.

Here is what I see in the logs
INFO: [75090] RESOLVERECIPIENTS request received for user account@domain.tld
INFO: [75090] Device entry exists for 1234HAHA, updating userAgent and 
version.
INFO: [75090] Request being handled for device: 1234HAHA, Supporting 
protocol version: 14.1, Using Horde_ActiveSync v2.19.4
INFO: [75090] GET VARIABLES: Array
INFO: [1234HAHA] Handling RESOLVERECIPIENTS command.
DEBUG: [75090] I  <ResolveRecipients:ResolveRecipients>
DEBUG: [75090] I   <ResolveRecipients:To>
DEBUG: [75090] I     account@domain.tld
DEBUG: [75090] I   </ResolveRecipients:To>
DEBUG: [75090] I   <ResolveRecipients:Options>
DEBUG: [75090] I    <ResolveRecipients:MaxAmbiguousRecipients>
DEBUG: [75090] I      0
DEBUG: [75090] I    </ResolveRecipients:MaxAmbiguousRecipients>
DEBUG: [75090] I    <ResolveRecipients:CertificateRetrieval>
DEBUG: [75090] I      2
DEBUG: [75090] I    </ResolveRecipients:CertificateRetrieval>
DEBUG: [75090] I   </ResolveRecipients:Options>
DEBUG: [75090] I  </ResolveRecipients:ResolveRecipients>
DEBUG: [75090] O  <ResolveRecipients:ResolveRecipients>
DEBUG: [75090] O   <ResolveRecipients:Status>
DEBUG: [75090] O    1
DEBUG: [75090] O   </ResolveRecipients:Status>
DEBUG: [75090] O   <ResolveRecipients:Response>
DEBUG: [75090] O    <ResolveRecipients:To>
DEBUG: [75090] O     account@domain.tld
DEBUG: [75090] O    </ResolveRecipients:To>
DEBUG: [75090] O    <ResolveRecipients:Status>
DEBUG: [75090] O     1
DEBUG: [75090] O    </ResolveRecipients:Status>
DEBUG: [75090] O    <ResolveRecipients:RecipientCount>
DEBUG: [75090] O     1
DEBUG: [75090] O    </ResolveRecipients:RecipientCount>
DEBUG: [75090] O    <ResolveRecipients:Recipient>
DEBUG: [75090] O     <ResolveRecipients:Type>
DEBUG: [75090] O      2
DEBUG: [75090] O     </ResolveRecipients:Type>
DEBUG: [75090] O     <ResolveRecipients:DisplayName>
DEBUG: [75090] O      My Name
DEBUG: [75090] O     </ResolveRecipients:DisplayName>
DEBUG: [75090] O     <ResolveRecipients:EmailAddress>
DEBUG: [75090] O      account@domain.tld
DEBUG: [75090] O     </ResolveRecipients:EmailAddress>
DEBUG: [75090] O     <ResolveRecipients:Certificates>
DEBUG: [75090] O      <ResolveRecipients:Status>
DEBUG: [75090] O       7
DEBUG: [75090] O      </ResolveRecipients:Status>
DEBUG: [75090] O      <ResolveRecipients:CertificateCount>
DEBUG: [75090] O       0
DEBUG: [75090] O      </ResolveRecipients:CertificateCount>
DEBUG: [75090] O     </ResolveRecipients:Certificates>
DEBUG: [75090] O    </ResolveRecipients:Recipient>
DEBUG: [75090] O   </ResolveRecipients:Response>
DEBUG: [75090] O  </ResolveRecipients:ResolveRecipients>
INFO: [75090] Maximum memory usage for ActiveSync request: 7953440 bytes.