I would ask, in which cases could an order not be saved in database after payment, or could be deleted. In my case when i look in the database, i cant find some order_id's. For example i find Order_id : 288 and 290 and can't find the order_id 289, although it's autoincremeted. I can't find an explanation for that
Having missing autoincrement is absolutely fine, as in case if stock reservation cannot be done, it would result in full revert of the transaction, but at the same time there could be other customers who succeed with the order, so next autoincrement value got used.
You should only worry about it if number of completed payments does not match number of orders in Magento.
UPDATE: Sorry, didn't read your title at first
Seems like you've run into this issue, I've answered before on this site: Price re-index causes DB deadlocks during checkout