One problem I see is that your DELETE will try to delete from both tables when a row exists in pxpl with WHERE pxpl.DeactivationTS < (NOW() - INTERVAL 24 HOUR). But the related row (through the FK) in proxies maybe related to more rows in pxpl that do not match the criteria. And because the FK has ON DELETE CASCADE, it will try to delete them as well. That maybe one reason for the deadlocks you see (when there is no ORDER BY).

You can try to delete only from the parent table and let the cascade action do its work and delete all the ratled rows in the child table, say with:

DELETE FROM proxies 
WHERE EXISTS
  ( SELECT 1 
    FROM proxy_xref_proxy_list AS pxpl 
    WHERE proxies.ID = pxpl.ProxyID
      AND pxpl.DeactivationTS < (NOW() - INTERVAL 24 HOUR)
  ) ;

You could even use ORDER BY this way, although I don't think you need it.