Why do these queries deadlock and how to work this around in MariaDB?
OR is terrible on performance, and probably equally bad on transaction locks.

pxpl.DeactivationTS IS NULL OR pxpl.DeactivationTS &gt;= ...


Instead of depending on NULL in that, consider storing a date in the future.  That way this would suffice:

pxpl.DeactivationTS &gt;= ...


EXISTS -- Since EXISTS stops at the first occurrence, LIMIT 1 is redundant.  Similarly, the inner ORDER BY seems fishy.

TINYTEXT -- This datatype has some minor disadvantages compared to VARCHAR(255)  Better yet, is to use VARCHAR with a realistic limit.

If those don't help enough, please provide a SELECT (possibly with a LEFT JOIN) that would list the rows that should be deleted.  With that, we might be able to devise a variation on the DELETE that will be more deadlock-proof.

If that, too, fails, then simply plan on handling deadlocks:  Detect them, then replay the transaction containing the DELETE.

This might be a better DELETE:

DELETE proxies FROM proxies
    LEFT JOIN proxy_xref_proxy_list AS pxpl
      ON proxies.ID = proxy_xref_proxy_list.ProxyID
    AND (proxy_xref_proxy_list.DeactivationTS IS NULL
      OR proxy_xref_proxy_list.DeactivationTS &gt;= (NOW() - INTERVAL 24 HOUR))
   WHERE proxy_xref_proxy_list.ProxyID IS NULL