Magento – Custom cron causing one page checkout deadlocks

We have created a Magento cron that is being run through cron.php. This cron updates certain orders to the 'canceled' order status:

    public function abandonedOrderCleanup() {
        $statusArray('custom_status');
        $collection = Mage::getResourceModel('sales/order_collection')->addFieldToFilter('status', array('in', $statusArray));
        Mage::getSingleton('core/resource_iterator')->walk($collection->getSelect(), array(array($this, 'cancelOrder')));
    }

    public function cancelOrder($orderData) {
      $order = Mage::getModel('sales/order')->setData($orderData['row']);
      if (!$order->getReadyToCancel()) {
              continue;
            }
            $order->cancel();
            $order->save();
    }

While it is running deadlocks are occasionally reported in exception.log that come from customers trying to place orders using the one page checkout:

2014-03-07T15:07:50+00:00 ERR (3):
exception 'PDOException' with message 'SQLSTATE[40001]: Serialization failure: 1213 Deadlock found when trying to get lock; try restarting transaction' in /var/www/magento1702/lib/Zend/Db/Statemen\
t/Pdo.php:228
Stack trace:
#0 /var/www/magento1702/lib/Zend/Db/Statement/Pdo.php(228): PDOStatement->execute(Array)
#1 /var/www/magento1702/lib/Varien/Db/Statement/Pdo/Mysql.php(110): Zend_Db_Statement_Pdo->_execute(Array)
#2 /var/www/magento1702/lib/Zend/Db/Statement.php(300): Varien_Db_Statement_Pdo_Mysql->_execute(Array)
#3 /var/www/magento1702/lib/Zend/Db/Adapter/Abstract.php(479): Zend_Db_Statement->execute(Array)
#4 /var/www/magento1702/lib/Zend/Db/Adapter/Pdo/Abstract.php(238): Zend_Db_Adapter_Abstract->query('INSERT INTO `sa...', Array)
#5 /var/www/magento1702/lib/Varien/Db/Adapter/Pdo/Mysql.php(419): Zend_Db_Adapter_Pdo_Abstract->query('INSERT INTO `sa...', Array)
#6 /var/www/magento1702/app/code/core/Mage/Sales/Model/Resource/Order/Abstract.php(177): Varien_Db_Adapter_Pdo_Mysql->query('INSERT INTO `sa...')
#7 /var/www/magento1702/app/code/core/Mage/Sales/Model/Abstract.php(51): Mage_Sales_Model_Resource_Order_Abstract->updateGridRecords('196465')
#8 /var/www/magento1702/app/code/core/Mage/Sales/Model/Order.php(2155): Mage_Sales_Model_Abstract->_afterSave()
#9 /var/www/magento1702/app/code/core/Mage/Core/Model/Abstract.php(319): Mage_Sales_Model_Order->_afterSave()
#10 /var/www/magento1702/app/code/core/Mage/Core/Model/Resource/Transaction.php(151): Mage_Core_Model_Abstract->save()
#11 /var/www/magento1702/app/code/core/Mage/Sales/Model/Service/Quote.php(189): Mage_Core_Model_Resource_Transaction->save()
#12 /var/www/magento1702/app/code/core/Mage/Sales/Model/Service/Quote.php(249): Mage_Sales_Model_Service_Quote->submitOrder()
#13 /var/www/magento1702/app/code/core/Mage/Checkout/Model/Type/Onepage.php(774): Mage_Sales_Model_Service_Quote->submitAll()
#14 /var/www/magento1702/app/code/core/Mage/Checkout/controllers/OnepageController.php(511): Mage_Checkout_Model_Type_Onepage->saveOrder()
#15 /var/www/magento1702/app/code/core/Mage/Core/Controller/Varien/Action.php(419): Mage_Checkout_OnepageController->saveOrderAction()
#16 /var/www/magento1702/app/code/core/Mage/Core/Controller/Varien/Router/Standard.php(250): Mage_Core_Controller_Varien_Action->dispatch('saveOrder')
#17 /var/www/magento1702/app/code/core/Mage/Core/Controller/Varien/Front.php(176): Mage_Core_Controller_Varien_Router_Standard->match(Object(Mage_Core_Controller_Request_Http))
#18 /var/www/magento1702/app/code/core/Mage/Core/Model/App.php(354): Mage_Core_Controller_Varien_Front->dispatch()
#19 /var/www/magento1702/app/Mage.php(683): Mage_Core_Model_App->run(Array)
#20 /var/www/magento1702/index.php(87): Mage::run('eur', 'website')
#21 {main}

We have tried to find a way to reliably replicate the issue so we can better address it. Even by adding 100k orders to a stage system and manually running the cron we have only once been able to experience the deadlock when manually placing payments through the checkout. In case it is of any consequence, this is how we have been generating the test orders:

for($i = 1; $i setProductId(1)->setQtyOrdered(3);
    $payment = Mage::getModel('sales/order_payment')->setMethod('payment_method_code');
    $order = Mage::getModel('sales/order')->setState('processing')->setStatus('custom_status')->addItem($item);
    $order->setPayment($payment);
    $order->save();
}

We need to run this cron on stores running CE 1.7.0.0 – 1.8.1.0.

What can we do to stop the deadlock from occurring?

Edit: A second question. How can we reliably replicate this deadlock?

I have created a second script that makes repeated POSTs using cURL to checkout/onepage/saveOrder to add c. 3 orders a second. I run this script while the cron is running (to update 100k orders). I thought this would cause a deadlock but so far it hasn't. (We're trying to replicate the problem consistently so we can properly test any solution.)