Are you using paypal IPN payment module? If yes, there must be an option to set (Should Products Stock be updated even when the payment is not yet COMPLETED) while configuring this module through admin -> modules -> payment.
All orders are saved in the database with status "Paypal Processing" before the customer is redirected to paypal site to make the payment. So even if the customer do not make the payment at paypal, the order is still there in admin with status "Paypal Processing" unless thety are dleted by admin.
You have to modify the code to restock the products when the status is changed to "cancelled"