To assist anyone else Ive found the cause.

I needed to Add a Non Clustered Index to Payloads(PayloadId) - Kindof a parent child relationship.

Looking at the Execution plan for the DELETE...