Message to Call Log Relationship

You're correct, this is not the easiest or most transparent task to accomplish.

Voicemails are stored in the Message Store and contain an ID for each message: voicemail/fax/sms.
Requests to Message Store can be filtered by type="VoiceMail", direction="Inbound", and dateFrom={{beginning_time_to_search_from}}

The response contains records, each record contains properties which can be used to map this type of reverse-lookup:
- uri: which has the URI to the associated Extension
- creationTime
- to: who called/created the voicemail
- from: the target for the voicemail

Requests to Call Log can be filtered by type="Voice", direction="Inbound", view="Detailed", and dateFrom/dateTo={{isolationTimeBasedOnMessageResponse}}

Each of the records will contain a "result" property which will be "VoiceMail" in the cases where a voicemail was left.

You can also reverse this and pull Call Logs, extracting where result=VoiceMail and then conduct the messageStore lookups for the appropriate Extensions using dateTo/dateFrom.